题目链接
题解
知识点：DFS序。
编号已经满足 dfs 序，因此对于边 \(t_v = (u,v), u < v\) ，有且仅有两条路径 \(v - 1 \to v, R_v \to R_v \bmod n + 1\) 会经过这条边，前者是进入子树 \(v\) 时经过，后者是离开子树 \(v\) 时经过。其中 \(R_v\) 表示子树 \(v\) 内的最大编号，我们可以用 dfs 预处理。
显然，当一条路径存在未确定的边时，它的距离等于路径上确定的边的边权和加上剩余未分配的权值（全给未确定的边即可）。
设总和为 \(ans\) ，最初 \(n\) 条路径的距离都是 \(0 +w\) ，因此 \(ans = nw\) 。
每次确定一个边权 \(y\)，未分配的权值将会减少 \(y\)，因此所有不经过这条边且存在未确定边的路径的距离都将减少 \(y\)，而经过这条边的路径的距离不会发生变化。设剩余存在未确定边的路径数为 \(rest\) ，那么一次操作后答案将更新为 \(ans - (rest - 2)y\) 。
此外，一次操作后，如果存在路径已经完全确定时，它们的距离就不能加上未分配的权值，假设 \(w'\) 是当前未分配的权值，那么需要将答案更新为 \(ans - w\) 。
最后，我们可以预处理每条路径未确定边的个数 \(cnt\) ，每次确定一条边，会更新经过它的两条路径的 \(cnt\) 值。当某条路径的 \(cnt\) 归零，表示它已经完全确定。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;vector<int> g[200007];
int cnt[200007];int R[200007];
void dfs(int u) {R[u] = u;for (auto v : g[u]) {dfs(v);R[u] = max(R[u], R[v]);}
}bool solve() {int n;ll w;cin >> n >> w;for (int i = 1;i <= n;i++) {cnt[i] = 0;g[i].clear();}for (int i = 2;i <= n;i++) {int p;cin >> p;g[p].push_back(i);}dfs(1);for (int i = 2;i <= n;i++) {cnt[i - 1]++;cnt[R[i]]++;}int rest = n;ll ans = n * w;for (int i = 1;i <= n - 1;i++) {int x;ll y;cin >> x >> y;cnt[x - 1]--;cnt[R[x]]--;w -= y;ans -= 1LL * (rest - 2) * y;if (cnt[x - 1] == 0) ans -= w, rest--;if (cnt[R[x]] == 0) ans -= w, rest--;cout << ans << ' ';}cout << '\n';return true;
}int main() {std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;
}
