C0843 [JSOI2016]轻重路径

JYY 最近学习了一种处理树形结构的高级技巧，叫「轻重路径剖分」。这种技术会将树中的边划分成轻边和重边。相连的重边会形成一些树上相离的路径。「轻重路径剖分」可以使得从树上任意一点走到根，都至多只会经过 $\mathcal{O} (\log N)$ 条不同的重路径。

如果你不了解轻重路径剖分，JYY 在这里简单介绍一下：对于一棵有根树中的任意一个点 $u$，我们用 $\text{size}(u)$ 表示其为根的子树中的点的数量。对于 $u$ 的所有孩子中，我们选出 $\text{size}$ 值最大的孩子 $v$，并将边 $(u,v)$ 设置成重边，$u$ 和其他孩子之间的边我们均设置为轻边。

为了简化问题，这里 JYY 仅考虑一棵 $N$ 个点的有根二叉树。这 $N$ 个点由 $1$ 到 $N$ 编号。并且如果 $u$ 存在两个 $\text{size}$ 值一样的孩子，则我们默认 $u$ 和其左孩子的连边为重边。

现在 JYY 希望执行额外 $Q$ 次删点操作，每次 JYY 会随机删掉一个当前二叉树的叶子节点，而你则需要动态的维护这棵树的轻重路径剖分。

为了方便输出，你只需要在每次操作后输出所有重边指向的点的权值和即可。

如果删除一个点之后，存在一个点 $u$ 拥有两个 $\text{size}$ 值一样的孩子，则我们保持 $u$ 在该操作执行之前的重边划分。

样例输入 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

样例输出 1

20
21
15
7
6
2
3
0