B. Iris 与树 详细题解

问题重述

给定一棵以 $1$ 为根的树，顶点编号满足 DFS 序性质（每个子树内编号连续）。每条边 $(i, p_i)$ 的权值 $t_i$ 未知，但满足 $\sum_{i=2}^n t_i = w$ 且 $t_i \ge 0$。有 $n-1$ 个事件，每个事件给定 $t_x = y$。每次事件后，对于每个 $i$（$1 \le i \le n$），需要最大化 $\operatorname{dist}(i, i \bmod n + 1)$，然后输出这 $n$ 个最大值的和。不同 $i$ 的最大化可以独立选择未知边权。

关键观察

观察 1：DFS 序性质

由于顶点按 DFS 序编号，每个子树 $i$ 的顶点编号构成连续区间：

$$[i, i + s_i - 1]$$

其中 $s_i$ 是子树 $i$ 的大小。

观察 2：边 $(i, p_i)$ 被哪些路径使用

对于边 $(i, p_i)$，考虑它连接的两个部分：

• 子树 $i$（编号 $i$ 到 $i + s_i - 1$）
• 树的其余部分

哪些 $j$ 到 $j+1$ 的路径会经过这条边？

• 如果 $j$ 和 $j+1$ 都在子树 $i$ 内，路径不经过该边
• 如果 $j$ 和 $j+1$ 都在子树外，路径不经过该边
• 只有当 $j$ 和 $j+1$ 一个在子树内、一个在子树外时，路径才经过该边

由于编号连续，恰好有两个这样的 $j$：

• $j = i - 1$（当 $i > 1$ 时）：$i-1$ 在子树外，$i$ 在子树内
• $j = i + s_i - 1$（当 $i + s_i \le n$ 时）：$i + s_i - 1$ 在子树内，$i + s_i$ 在子树外

因此，每条边 $(i, p_i)$ 最多被两条路径使用：

• 路径 $P_1$：连接 $(i-1, i)$（如果 $i > 1$）
• 路径 $P_2$：连接 $(i + s_i - 1, i + s_i)$（如果 $i + s_i \le n$）

记 $c_1[i]$ 和 $c_2[i]$ 为经过边 $i$ 的两条路径的编号（路径按起点编号标识）。

观察 3：路径长度的计算

对于路径 $j$（连接 $j$ 和 $j+1$），其长度等于经过的所有边的权值之和：

$$\operatorname{dist}(j, j+1) = \sum_{e \in \text{path}(j)} t_e $$

观察 4：最大化策略

当某些边权未知时，要最大化某条路径的长度：

• 将所有权重分配给该路径上的未知边
• 其他路径不受影响（因为不同路径的最大化是独立的）

具体地，设路径 $j$ 上已知边权之和为 $S_j$，未知边数量为 $u_j$。那么最大可能长度为：

$$S_j + (w - \text{所有已知边权之和})$$

但这里需要注意：不同路径共享未知边时，不能同时分配全部剩余权重。然而题目说明：不同 $i$ 的最大化可以独立选择未知边权。这意味着我们可以为每条路径分别考虑最优分配，即每条路径都可以假设自己独享所有剩余权重。

观察 5：更简单的计算方式

设总已知边权和为 $sum$。对于路径 $j$：

• 如果路径上所有边的权值都已确定，则长度固定为 $S_j$
• 否则，可以给该路径上的某条未知边分配剩余权重 $w - sum$，长度变为 $S_j + (w - sum)$

但需要确保该未知边确实在路径上。实际上，每条路径的"自由度"取决于其上是否有未知边。

观察 6：标程的巧妙方法

标程维护了两个关键数组：

• len[j]：路径 $j$ 上未知边的数量
• c1[x] 和 c2[x]：经过边 $x$ 的两条路径的编号

当一条边的权值被确定后：

• 该边从所有经过它的路径中"消失"（即该边不再是未知的）
• 如果某条路径的所有边都已知（len[j] == 0），则该路径不再参与"灵活分配"

最终答案的计算公式：

$$\text{ans} = 2 \cdot sum + \text{sur} \cdot (w - sum) $$

其中：

• $sum$：当前已确定的边权和
• $sur$：尚未被完全确定的路径数量（即至少还有一条未知边的路径数）
• 因子 $2$ 是因为每条路径对应两个方向？实际上需要仔细分析

算法步骤

1. 预处理：

   • 读入 $n, w$ 和父节点数组 $p_i$
   • 计算每个节点的深度 dep[i]
   • 对于每条路径 $j$（连接 $j$ 和 $j+1$），找出它经过的所有边，并记录每条边被哪些路径使用

2. 初始化：

   • len[j] = 路径 $j$ 上的边数（初始时所有边未知）
   • sur = $n$（所有路径最初都未完全确定）

3. 处理事件：

   • 读入 $x, y$，表示 $t_x = y$
   • $sum$ 增加 $y$
   • 对于经过边 $x$ 的两条路径 $c_1[x]$ 和 $c_2[x]$：
     • len[c] 减 $1$
     • 如果 len[c] 变为 $0$，则 sur 减 $1$
   • 输出 $2 \cdot sum + sur \cdot (w - sum)$

时间复杂度

• 预处理路径：$O(n)$（每条边最多被两条路径使用）
• 每个事件：$O(1)$
• 总复杂度：$O(n)$

完整代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200001;
int fa[MAXN], dep[MAXN];
int c1[MAXN], c2[MAXN], len[MAXN];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        long long w;
        cin >> n >> w;
        
        for (int i = 2; i <= n; i++) {
            cin >> fa[i];
        }
        
        // 计算深度
        dep[1] = 0;
        for (int i = 2; i <= n; i++) {
            dep[i] = dep[fa[i]] + 1;
        }
        
        // 初始化
        for (int i = 1; i <= n; i++) {
            len[i] = 0;
            c1[i] = c2[i] = 0;
        }
        
        // 预处理每条路径 j (连接 j 和 j+1) 经过的边
        for (int j = 1; j <= n; j++) {
            int x = j;
            int y = (j == n ? 1 : j + 1);
            
            while (x != y) {
                if (dep[x] < dep[y]) swap(x, y);
                // 边 x (连接 x 和 fa[x]) 被路径 j 使用
                if (c1[x] == 0) c1[x] = j;
                else c2[x] = j;
                x = fa[x];
                len[j]++;
            }
        }
        
        long long sum = 0;
        int sur = n;  // 尚未完全确定的路径数量
        
        for (int i = 1; i < n; i++) {
            int x;
            long long y;
            cin >> x >> y;
            
            sum += y;
            
            // 更新经过边 x 的两条路径
            if (c1[x] && --len[c1[x]] == 0) sur--;
            if (c2[x] && --len[c2[x]] == 0) sur--;
            
            long long ans = 2 * sum + sur * (w - sum);
            cout << ans << " \n"[i == n - 1];
        }
    }
    
    return 0;
}

代码说明

1. 深度计算：dep[i] 表示节点 $i$ 的深度，用于 LCA 计算
2. 路径预处理：对于每条路径 $(j, j+1)$，向上爬到 LCA，记录经过的边
3. 边与路径的映射：c1[x] 和 c2[x] 记录经过边 $x$ 的两条路径
4. 长度维护：len[j] 表示路径 $j$ 上未知边的数量
5. 答案计算：
   • $2 \cdot sum$：已确定边对答案的贡献（每条边被两条路径使用？需要验证）
   • $sur \cdot (w - sum)$：剩余权重分配给未完全确定的路径

示例验证

以第二个测试用例为例：

• $n=4, w=9$，树边：$p_2=1, p_3=1, p_4=1$（星形树）
• 路径：
  • $j=1$：连接 $1-2$，经过边 $2$
  • $j=2$：连接 $2-3$，经过边 $2$ 和 $3$
  • $j=3$：连接 $3-4$，经过边 $3$ 和 $4$
  • $j=4$：连接 $4-1$，经过边 $4$

事件1：$t_2=2$，$sum=2$

• 边 $2$ 经过路径 $1$ 和 $2$，len[1] 和 len[2] 各减 $1$
• 路径 $1$ 的 len 变为 $0$（只有边 $2$），sur 减 $1$
• 路径 $2$ 的 len 变为 $1$（还剩边 $3$）
• sur = 3（路径 $2,3,4$ 未完全确定）
• 答案 = $2 \times 2 + 3 \times (9-2) = 4 + 21 = 25$ ✓

总结

本题的核心技巧：

1. 利用 DFS 序性质，发现每条边最多被两条路径使用
2. 将问题转化为维护每条路径上未知边的数量
3. 答案公式 $2 \cdot sum + sur \cdot (w - sum)$
4. $O(n)$ 预处理和 $O(1)$ 事件处理