Dp on trees again

Can anyone help me with this question https://codeforces.com/problemset/problem/1153/D.
@vijju123,@anon55659401,@aryanc403,@ssjgz,@l_returns
Please Help…anyone??

1 Like

This is my solution : https://codeforces.com/contest/212/submission/63764817
I will try my best to explain.

WALKTHROUGH :
For every node there can be a subtree and an outer tree(tree excluding the subtree), so first we need to build the 2 arrays “in” and “out” which store the subtree size and outer tree size respectively , this is calculated in “dfs” method. Then for each node we can split all the child nodes and parent node in 2 sets, so we need to find the maximum split into 2 sets. Note that any of the combination of in and out can form the split. In order to find this we can simply iterate over all nodes and select the node which has at least 2 branches, so that for each branch we can have a specific network cafe ie. McD or BurgerKing , and then select the maximum size for the total branches for all nodes.

The second dfs calculates the maximum possible size in the tree , let it be “ans”.
After this we need to build the solution for the same.
The “ans” which we calculated has an upper bound of 5000. so we consider all the numbers “j” from 1 to “ans” and for each node in the tree which has “ans” as sum of branches (which are the subtree sizes for each direct neighbour of the node) , we try to add these branch sizes to a list and then solve a subset sum subproblem for j. As we can solve for a particular j for any node then we mark it and try to solve for rest of the numbers from 1 to ans.
“_left” is a unordered_set which keeps the track the numbers for which the subset sum problem is left to be solved.

then we iterate over all the numbers(i) from 1 to ans and if that number(i) could not be solved by any of the nodes then we leave it else we add {i , ans-i} to a sorted set and print it in the end.

Please feel free to ask any part u didn’t understand.

2 Likes

Got it ,Thanks!!

1 Like