Dynamic Heavy-Light Path Decomposition on a Binary Tree

JYY has recently been studying an advanced technique for processing tree structures called Heavy-Light Decomposition. In this method the edges of a tree are classified as either heavy or light. Consecutive heavy edges form paths along the tree, and it can be shown that on any path from a node to the root there are at most $O(\log N)$ different heavy paths.

For the purpose of this problem, you are given a rooted binary tree with $N$ nodes (numbered $1$ through $N$). The heavy-light decomposition is defined as follows. For any node $u$, let $\text{size}(u)$ be the number of nodes in the subtree rooted at $u$. Among the children of $u$, the child with the maximum $\text{size}$ is connected by a heavy edge and the other child (if any) is connected by a light edge. In the case where $u$ has two children with equal $\text{size}$, if such a tie occurs after a deletion operation, you must retain $u$’s heavy edge assignment from before the deletion; for the initial tree, when a tie occurs choose the left child as the heavy edge.

JYY will perform $Q$ deletion operations. In each operation a leaf of the current tree is removed (it is guaranteed that the deleted node is indeed a leaf). After each deletion, you are to dynamically maintain the heavy-light decomposition (as described above) on the remaining tree and output the sum of the node numbers to which all heavy edges point. That is, for every node $u$ in the tree that currently has a heavy edge from it to one of its children $v$, you should sum up $v$ over all such nodes $u$.

inputFormat

The first line contains two integers $N$ and $Q$ ($1 \le N, Q \le 10^5$) representing the number of nodes in the tree and the number of deletion operations.

The next $N$ lines each contain two integers; the $i$-th line contains $L_i$ and $R_i$ representing the left and right child of node $i$ respectively. A value of 0 indicates a missing (null) child. It is guaranteed that the given structure forms a rooted binary tree with root 1.

Each of the next $Q$ lines contains a single integer representing the label of the leaf node to be deleted in that operation. It is guaranteed that the deletion order is valid.

outputFormat

Output $Q$ lines. For each deletion operation, output the sum of the node numbers which are the endpoints of heavy edges in the current tree (i.e. for every node $u$ with a heavy edge to $v$, sum up $v$).

sample

5 3
2 3
4 5
0 0
0 0
0 0
4
5
3

7
2
2