404345: GYM101484 F No Link, Cut Tree!

Marge is already preparing for Christmas and bought a beautiful tree, decorated with shiny ornaments. Her Christmas tree can be represented as a complete binary tree composed of N nodes, numbered from 1 to N and rooted on node 1. Each node has an integer value associated to it, representing its shininess.

The shininess of the h - th level of the tree is the sum of the shininess of all the nodes with depth h and the shininess of the tree is the largest value of shininess of its levels.

Nicoleta has a crush on a girl and wants to give her a part of Marge's beautiful tree. To do so, he will choose a node u and give his crush the subtree rooted at node u, including u. However, he doesn't want to get in (too much) trouble with Marge, so he will consider some candidates before making the cut.

Nicoleta has M candidate nodes to be the root of the cut subtree. For each candidate, Nicoleta wants to know what is the value of shininess of the remaining tree.

The first line of the input contains a three integers N (2 ≤ N ≤ 10⁵) and M (1 ≤ M ≤ 10⁵) and w (0 ≤ w ≤ 10⁴), indicating, respectively, the number of nodes of the tree, the number of candidate nodes and the shininess of node 1.

Each of the next N - 1 lines contains three integers u (2 ≤ u ≤ N) , v (1 ≤ v ≤ N) and w (0 ≤ w ≤ 10⁴), indicating that node u is a child of node v and has shininess w.

M lines follow, each with a single integer u (2 ≤ u ≤ N), indicating the number of a candidate node.

For each candidate node, in the order that they appear in the input, output a single line containing a single integer: the shininess of the remaining tree.

6 2 3
4 1 1
5 1 4
2 4 7
3 4 6
6 5 5
4
5

5
13

More about complete binary trees: https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees