题意理解

我们有一棵有根树（节点 0 为根），每个节点 ( u ) 定义了一个值 ( r_u ) 表示：从 ( u ) 出发，向下延伸的最长链的长度（这里的链是简单路径，且必须从 ( u ) 开始向下走）。

题目要求： [ \text{答案} = \sum_{u=0}^{N-1} r_u ] 并且有 ( Q ) 次操作，每次将某条边的长度增加 ( add_i )，每次操作后都要输出当前答案（模 ( 10^9+7 )）。

初步分析

设 ( dis[u] ) 表示从根节点 0 到节点 ( u ) 的距离（边权和）。

对于节点 ( u )，( r_u ) 实际上是： [ r_u = \max_{v \in \text{subtree}(u)} (dis[v]) - dis[u] ] 因为从 ( u ) 出发到子树中某个最远的叶子 ( v ) 的距离 = ( dis[v] - dis[u] )。

所以： [ \sum_{u} r_u = \sum_{u} \left( \max_{v \in \text{subtree}(u)} dis[v] - dis[u] \right) ] 设 ( M_u = \max_{v \in \text{subtree}(u)} dis[v] )，则： [ \text{答案} = \sum_u M_u - \sum_u dis[u] ] 注意 (\sum_u dis[u]) 就是所有节点到根的距离之和。

动态维护

当某条边 ( (p_v, v) ) 的长度增加 ( add ) 时：

• 以 ( v ) 为根的子树中所有节点的 ( dis ) 都会增加 ( add )。
• 因此 (\sum_u dis[u]) 会增加 ( sz[v] \times add )，其中 ( sz[v] ) 是子树 ( v ) 的大小。
• 同时，对于所有祖先 ( x ) 的 ( M_x ) 可能也会变化，因为子树 ( v ) 中的最大 ( dis ) 增加了。

关键难点

维护 ( \sum_u M_u ) 是本题的核心。

观察：

• ( M_u = \max( M_{c_1}, M_{c_2}, \dots, M_{c_k}, dis[u] ) )，其中 ( c_i ) 是 ( u ) 的孩子。
• 实际上 ( M_u ) 等于子树 ( u ) 中叶子节点的最大 ( dis ) 值。
• 当更新一条边时，子树 ( v ) 内的 ( M_x ) 都会增加 ( add )，但祖先的 ( M_x ) 可能不变，也可能变为新的来自 ( v ) 子树的最大值。

解法思路

使用树链剖分 + 多棵线段树 + 树状数组来高效维护这些信息。

主要结构：

1. 树链剖分

   • 把树分成重链，方便路径操作。
   • 建立 DFS 序，使得子树对应连续区间。

2. Segment 线段树

   • 维护区间 ( dis ) 的最大值，支持区间加。

3. 另一棵复杂线段树

   • 维护每个节点的 ( M_u ) 的“次大值”相关信息，用于更新时判断是否要改变祖先的 ( M_u )。

4. 树状数组 (BIT)

   • 维护每个节点的当前 ( M_u ) 值，用于快速单点查询和更新。

5. bel[u]

   • 记录节点 ( u ) 的 ( M_u ) 是由哪个孩子的子树贡献的（重链头信息）。

更新过程

当边 ( (p_x, x) ) 增加 ( add )：

1. 更新子树 ( x ) 的 ( dis )（Segment 树区间加）。

2. 更新子树 ( x ) 的 ( M ) 值（另一棵线段树区间加）。

3. 沿着祖先链向上，检查每个祖先 ( y )：

   • 如果新的来自 ( x ) 子树的 ( M_x ) 大于 ( y ) 当前的 ( M_y )，则更新 ( M_y )。
   • 否则如果 ( x ) 不是 ( M_y ) 的贡献者，则只需更新 ( y ) 的次大值信息。

4. 更新 (\sum dis) 和 (\sum M)，计算答案： [ \text{ans} = \sum M_u - \sum dis[u] ] 即代码中的 (sum[1] + sum2 + mod - S * 2 % mod) % mod，其中：

   • sum[1] 是某棵线段树维护的与次大值相关的和
   • sum2 是 (\sum M_u)
   • S 是 (\sum dis[u])

样例验证

以题目样例 N=5 为例，初始所有边长为 0，所以所有 ( dis[u] = 0 )，所有 ( M_u = 0 )，答案 = 0。

第一次更新：边 (0,1) 增加 2

• 子树 1 的 dis 和 M 都增加 2
• 节点 1 的 r_1 变为 2，节点 0 的 r_0 变为 2
• 答案 = 2（节点 0 和 1 的 r 值之和）

依此类推，符合输出。

复杂度

• 树链剖分 + 线段树：每次更新 O(log²N) 或 O(logN)
• 总复杂度 O((N+Q) log²N) 或 O((N+Q) logN)，可过 N,Q ≤ 1e5

总结

这道题的关键是将问题转化为维护 (\sum M_u - \sum dis[u])，并利用树链剖分和线段树高效处理子树更新与祖先链的最大值传播。代码中复杂的线段树和 bel 数组都是为了在更新时快速判断是否需要更新祖先的 ( M_u )，从而保证复杂度。