题目理解

我们有一棵有根二叉树，初始时每个节点有两个子节点（可能为空）。
我们需要实现轻重路径剖分：

• 对于每个节点 $u$，选择 $\mathrm{size}$ 最大的子节点作为重儿子（如果左右子节点 $\mathrm{size}$ 相同，则选左子节点）。
• 重边是 $u$ 到重儿子的边。
• 题目要求输出所有重边指向的点的编号之和（即所有重儿子的编号和）。

然后进行 $Q$ 次操作，每次删除一个叶子节点，删除后要更新树的 $\mathrm{size}$ 和重边选择，并输出当前的重儿子编号和。

关键点：删除叶子后，如果某个节点的左右子节点 $\mathrm{size}$ 变得相等，我们保持原来的重边选择不变（即不改变重儿子）。

思路分析

1. 初始建树与 size 计算

• 用邻接表或直接 lch[i], rch[i] 存储左右孩子。
• 递归或从叶子向上 BFS/DFS 计算初始 $\mathrm{size}$。
• 同时记录每个节点的重儿子 heavy[u]。

2. 删除叶子的影响

删除一个叶子 $x$ 后：

• 它的父节点 $\mathrm{size}$ 会减少 1。
• 这个变化可能向上传播到根，路径上的节点的 $\mathrm{size}$ 都会减少 1。
• 对于路径上的每个节点 $u$，$\mathrm{size}[lch]$ 和 $\mathrm{size}[rch]$ 可能变化，可能影响重儿子的选择。

3. 重儿子更新的条件

设当前节点 $u$，左右子节点 $l$、$r$：

• 如果 $\mathrm{size}[l] > \mathrm{size}[r]$，则重儿子是 $l$。
• 如果 $\mathrm{size}[l] < \mathrm{size}[r]$，则重儿子是 $r$。
• 如果 $\mathrm{size}[l] = \mathrm{size}[r]$，则保持原来的重儿子（即不更新）。

所以只有 $\mathrm{size}$ 变化导致大小关系改变且不相等时，才更新重儿子。

4. 高效维护

• 直接模拟每次删除后重新计算整棵树 $\mathrm{size}$ 和重儿子会超时（$O(NQ)$ 不可行）。
• 我们注意到，删除叶子只会影响从该叶子到根的路径上的节点。
• 因此可以：
  1. 从叶子向上走到根，更新 $\mathrm{size}$。
  2. 检查路径上的每个节点是否需要更新重儿子。
  3. 如果重儿子改变，则从总和中减去旧重儿子的编号，加上新重儿子的编号。

复杂度：每次删除操作，路径长度 $O(\log N)$（树高），总复杂度 $O((N+Q)\log N)$。

算法步骤

1. 读入：存储树结构，确定根（没有父节点的节点）。
2. 初始化：
   • 计算 $\mathrm{size}$（DFS 后序遍历）。
   • 确定每个节点的重儿子，计算初始总重儿子编号和。
3. 处理删除操作：
   • 对于每个被删除的叶子 $x$：
     • 将其标记为已删除（$\mathrm{size}=0$，且不再参与计算）。
     • 从 $x$ 的父节点开始向上到根：
       • 旧 $\mathrm{size}$ 记为 old_size，新 $\mathrm{size}$ 减 1。
       • 更新 $\mathrm{size}$。
       • 检查该节点的重儿子是否需要更新：
         • 比较左右子节点的 $\mathrm{size}$（如果子节点被删除，则 $\mathrm{size}=0$）。
         • 如果左右 $\mathrm{size}$ 相等，保持原重儿子。
         • 否则选择 $\mathrm{size}$ 大的作为新重儿子。
         • 如果重儿子改变，更新总和。
     • 输出当前总和。

复杂度分析

• 初始 DFS：$O(N)$。
• 每次删除：从叶子到根路径长度 $O(\log N)$，每次更新 $O(1)$。
• 总复杂度：$O(N + Q\log N)$，可满足 $N \le 2\times 10^5$。