P5773 [JSOI2016] Heavy-Light Paths

JYY has recently learned an advanced technique for processing tree structures, called “heavy-light decomposition”. This technique divides the edges of a tree into light edges and heavy edges. Connected heavy edges form several vertex-disjoint paths on the tree. With heavy-light decomposition, starting from any node and walking to the root, you will pass through at most $(\log N)$ different heavy paths. If you are not familiar with heavy-light decomposition, JYY gives a brief introduction here. For any node $u$ in a rooted tree, let $size(u)$ denote the number of nodes in the subtree rooted at $u$. Among all children of $u$, choose the child $v$ with the largest $size$ value, and mark the edge $(u,v)$ as a heavy edge. All edges between $u$ and its other children are marked as light edges. To simplify the problem, JYY only considers a rooted binary tree with $N$ nodes. The $N$ nodes are numbered from $1$ to $N$. If a node $u$ has two children with the same $size$ value, then by default the edge between $u$ and its left child is the heavy edge. Now JYY wants to perform an additional $Q$ node-deletion operations. Each time, JYY will randomly delete a current leaf node of the binary tree, and you need to dynamically maintain the heavy-light decomposition of this tree. For convenient output, after each operation you only need to output the sum of the indices of all nodes pointed to by heavy edges. If after deleting a node, there exists a node $u$ whose two children have the same $size$ value, then we keep the heavy-edge choice of $u$ the same as it was before this operation was performed.

The first line contains an integer $N$. The next $N$ lines: the $i$-th line contains two integers $L_i, R_i$, representing the index of the left child and the right child of node $i$. $L_i = 0$ means node $i$ has no left child, and $R_i = 0$ means node $i$ has no right child. The $(N+2)$-th line contains an integer $Q$, indicating the number of deletion operations performed by JYY. The $(N+3)$-th line contains $Q$ space-separated positive integers, representing the indices of the leaves deleted by JYY. The input guarantees that each deletion operation deletes a leaf.

Output $Q + 1$ lines. Each line contains one integer: the sum of the indices of all nodes pointed to by heavy edges in the heavy-light decomposition. The first line corresponds to the initial decomposition, and the following $Q$ lines correspond to the decomposition after each deletion operation.

For $30\%$ of the testdata, $N \le 1000$. For $50\%$ of the testdata, $N \le 5 \times 10^4$. For all testdata, $N \le 2 \times 10^5$. Translated by ChatGPT 5