Ohline and Awlean are greedy for toffees

All submissions for this problem are available.
You are given 2 undirected trees with N nodes each. Each node has a toffee with a label of a number. You start at the root of both trees, that is node 1. At each turn you can do one of the following:
 Move to an adjacent unvisited node in Tree 1
 Move to an adjacent unvisited node in Tree 2
 If it has a toffee, take out a toffee from your current node in Tree 1 and give it to Ohline
 If it has a toffee, take out a toffee from your current node in Tree 2 and give it to Awlean
 Stop making anymore moves.
Ohline and Awlean are extremely volatile. They will start fighting if they don’t have the same number of toffees of each label in the end. Also, at any turn, if Ohline has 1 extra toffee then the next toffee should go to Awlean and should have the same label. Similarly, if Awlean has 1 extra toffee, the next toffee should go to Ohline and should have the same label.
Find the highest number of toffees (since it’s the same for both, counting for any one person) that can be given while preventing a fight at all instances.
Input
The first line contains a single integer N.
The second line contains N space separated numbers, the respective value of the nodes of Tree 1
The third line contains N space separated numbers, the respective value of the nodes of Tree 2.
The next N1 lines contain 2 integers, x and y, meaning that there is an undirected edge from x to y in Tree 1.
The next N1 lines contain 2 integers, x and y, meaning that there is an undirected edge from x to y in Tree 2.
Output
A single integer, the maximum number of toffees you can give to one of them.
Constraints
N<=2000, 1 <= Max(Toffee Type) <= 25
Subtask 1 (15 Points): N<=25
Subtask 2 (15 Points): N<=75
Subtask 3 (20 Points): N<=250
Subtask 3: (50 Points): N<=2000
Example
Input: 4 2 2 3 2 2 4 2 1 1 2 2 3 3 4 1 2 1 3 3 4 Output: 2
Author:  harrycoda 
Tags  harrycoda 
Date Added:  17112017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions