Problem Link
Difficulty
SIMPLE-EASY
Pre-requisites
Simple Math
Problem
You are given partial information of a binary tree: for each node, its id, and the sum of the ids of its children. This sum is 0 if the node is a leaf, and if the node has just one child, then it is equal to the child’s id. Given this, you are asked to output ids of all possible roots of such a tree, given that such a tree does exist.
Explanation
The possible root node is unique (if it exists). Since we are given that a tree exists, finding the root node’s id is as simple as follows.
Denote by “id(node v)” the id of the node v, and “sid(node v)” the sum of the id’s of v’s children. Consider x = sum(id(v) - sid(v)) over all nodes v. If a binary tree exists, then its root node has to have id x. This is because, for each node v other than the root, its id is counted once in the sum (as id(v)) and it cancels out once in the sum (as -sid(v’s parent)). Since the root node doesn’t have a parent, its id is left uncanceled in the sum.
The constraints N <= 30 were left to trick some people into trying out brute force solutions. The test-data however does not allow for such solutions to pass.
One possible brute force solution requires you to store all possible subtrees rooted at a particular vertex, and then for each vertex t, and possible children-pairs u,v test if t with u and v can form a possible subtree (by merging two subtrees rooted at u and v). The main issue to be handled here, is to ensure that the considered subtrees at u and v to be merged are disjoint.
This can be done by storing vector dp[node u] which stores bitmasks of all possible subtrees rooted at u. Finally check if there exists a vertex on which a subtree rooted includes all vertices.
Unfortunately the tests included cases where there were as many as 10^4 possible bitmasks for subtrees rooted at a node, and hence such an attempt to merge subtrees would have tried 10^4 * 10^4 possibilities to merge. Such an approach would time out.
Author’s Solution
Can be found here
Tester’s Solution
Can be found here
sadly i started in the wrong direction 
good work by the problem setter! 
