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.
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 N-1 lines contain 2 integers, x and y, meaning that there is an undirected edge from x to y in Tree 1.
The next N-1 lines contain 2 integers, x and y, meaning that there is an undirected edge from x to y in Tree 2.
A single integer, the maximum number of toffees you can give to one of them.
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
Input: 4 2 2 3 2 2 4 2 1 1 2 2 3 3 4 1 2 1 3 3 4 Output: 2
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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|
Fetching successful submissions