Heavy-Light Decomposition - 문제

树链剖分（Heavy-Light decomposition）是一种将树剖分为若干条路径的方法，使得从任意节点走到树根的过程中，路径的切换次数为 $O(\log n)$。在本题中，你需要维护一棵二叉树的树链剖分，这棵树的叶子节点会被逐个删除。

考虑一棵拥有 $n$ 个节点的二叉树 $T$，节点编号为 $1$ 到 $n$。每个节点可以有一个左儿子和一个右儿子。编号为 $1$ 的节点是树的根，它不是任何其他节点的儿子。其余每个节点都是某个节点的儿子。没有儿子的节点被称为叶子。对于每个节点，该节点的大小（size）是指其子树中的节点个数。

如果从节点 $u$ 指向其儿子 $v$ 的边满足：$v$ 的大小大于 $u$ 的另一个儿子 $w$ 的大小，或者 $v$ 是 $u$ 的唯一儿子，则称这条边为重边（heavy edge）。如果 $u$ 有两个儿子且它们的大小相同，则在最开始时，从 $u$ 出发的重边指向其左儿子。

首先，你必须找出树中所有的重边，并输出它们所指向的节点编号之和。之后，你必须处理 $m$ 次操作：从树中删除叶子节点 $u_i$，更新所有的重边，并输出当前重边所指向的节点编号之和。如果在删除节点后，某个节点 $u$ 的两个儿子大小相同，则从 $u$ 出发的重边保持不变。

输入文件包含多组测试数据。

每组测试数据的第一行包含一个整数 $n$ — 树中的节点数（$2 \le n \le 200\,000$）。

接下来的 $n$ 行包含对树的描述。其中第 $i$ 行包含两个整数 $L_i$ 和 $R_i$ — 第 $i$ 个节点的左儿子和右儿子的编号，如果第 $i$ 个节点没有对应的儿子，则为 0。

接下来的一行包含一个整数 $m$ — 要删除的叶子节点数（$1 \le m \le n - 1$）。

接下来的一行包含 $m$ 个整数 $u_1, u_2, \dots, u_m$ — 要删除的节点。保证在进行之前的所有删除操作后，节点 $u_i$ 确实是一个叶子节点。

输入以一行 $n = 0$ 结束，该行不需要处理。一个输入文件中所有测试数据的 $n$ 之和不超过 $200\,000$。

对于每组测试数据，输出 $m + 1$ 个整数。其中第一个整数必须是初始树中重边所指向的节点编号之和。接下来的每个整数必须是删除对应叶子节点后该和的值。

8
2 3
4 5
0 0
6 7
0 8
0 0
0 0
0 0
7
6 7 8 5 4 2 3
0

QOJ.ac