Company: Hewlett
Difficulty: medium
No Ancestor Subset You are given a tree with tree_nodes nodes, numbered from 1 to tree_nodes (1-based indexing). Node i has an associated weight weight[i] . The tree is rooted at node 1 . A subset of nodes is called good if there is no pair of nodes in it where one node is an ancestor of the other. Find the maximum possible sum of weights of a good subset. Note: A node u is an ancestor of a node v if u lies on the direct path from the root to v . A node is not an ancestor of itself, so any single node on its own forms a good subset. Input Format The first line contains two space-separated integers tree_nodes and tree_edges , where tree_edges = tree_nodes - 1 . Each of the next tree_edges lines contains two space-separated integers tree_from[i] and tree_to[i] , describing an undirected edge of the tree. The edges may be listed in any order and either endpoint may be written first. The next line contains a single integer equal to tree_nodes , the size of the weight array. Each of the nex