原题链接：https://codeforces.com/contest/2006/problem/B （D1 的 B 题，D2 的 E 题）
因赛时想复杂了没做出来导致渡劫失败 ( 1859 \rightarrow 1891 )，赛后补了一下发现竟然比 D 还好写 QwQ
题目大意
给定一个根为 1 ，且编号满足 DFS 序的树，令 \operatorname{dist}(u, v) 为树中顶点 u 和 v 之间路径的边权和。起初，每条边的边权都是未知的。接下来有 n - 1 次操作，每次操作将 t_x 赋值为 y ，在操作后需要输出目前
\sum_{i = 1}^n\operatorname{dist}(i, i \bmod n + 1) 可能的最大值。
思路
设进行到第 i 次操作后的边权为 sum_i 。
对于已经确定的边，由于树的编号满足 DFS 序，因此这些边对当前答案的贡献均为两次，即 2 \cdot sum_i，接下来只需要考虑未确定的边对答案的贡献。
一条边在 DFS 的过程中会被经过至少两次，即存在两对点 (i, i\bmod n + 1) ，它们之间的路径经过边 u 。设边 u 编号较小的顶点为 v，则这两对点分别为 (v-1,v) 与 (v + size\_v,(v+size\_v)\bmod n + 1)，其中 size_v 为点 v 的子树大小，可以很容易地用 DFS 求出。
然后就需要考虑上述两对点之间的路径是否已经全部确定了。若已经全部确定，则无需继续考虑（因为其贡献已经包含在上述的 2 \cdot sum\_i 中了），否则可以令其中一个未确定的边的边权为 w - sum\_i ，即此路径会产生 w - sum_i 的额外贡献，也就是说只需要找到还有多少条路径上的边没有被全部确定就可以了。
为了维护上述信息，可以开一个 len 数组来存储每条路径上还剩多少条边未被赋值，其初始值就是路径长度，每次进行赋值操作时对包含对应边的两条路径自减即可。那么，如何计算初始路径长度呢？只需要在 DFS 的过程中额外维护每个点的深度信息，即可通过两点的深度差快速算出长度。令 cnt 为 len 数组中非零数的个数（非零意味着这条路径上的边没有被全部确定），可以得出 ans = cnt \cdot (w - sum) + 2 \cdot sum。
时间复杂度为 O(n)。
实现
#include <bits/stdc++.h>
#define CNO cout << "NO\n"
#define CYES cout << "YES\n"
#define endl '\n'
#define ls id << 1
#define rs id << 1 | 1
#define llen (mid - l + 1)
#define rlen (r - mid)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long double ld;
typedef __int128 i128;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll mod = 998244353;
const int N = 200010;
ll n, w, x, y, arr[N], p[N], d[N], num[N], dp[N];
ll ans = 0;
string str;
vector<int> g[N];
void dfs(int x, int de) {
d[x] = de;
for (int i : g[x]) {
dfs(i, de + 1);
dp[x] += dp[i] + 1;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
cin >> T;
while (T--) {
cin >> n >> w;
for (int i = 1; i <= n; ++i) {
g[i].clear();
dp[i] = 0;
}
for (int i = 2; i <= n; ++i) {
cin >> p[i];
g[p[i]].push_back(i);
}
dfs(1, 1);
ans = w * n;
for (int i = 1; i <= n; ++i) {
if (i != n)
num[i] = d[i] - d[i % n + 1] + 2;
else
num[i] = d[n] - d[1];
}
ll sum = 0, cnt = n;
for (int i = 1; i < n; ++i) {
cin >> x >> y;
sum += y;
num[x - 1]--, num[x + dp[x]]--;
if (!num[x - 1]) cnt--;
if (!num[x + dp[x]]) cnt--;
cout << cnt * (w - sum) + 2 * sum << ' ';
}
cout << endl;
}
return 0;
}
评论