题解 CF1632E2 【Distance Tree (hard version)】
kradcigam
·
·
题解
题意：有一棵 n 个点的树，每条边长度为 1。现在加一条权值为 x 的边，最小化 f(x) = \max\limits_{i = 1} ^ {n} d_i。其中 d_i 表示点 1 到点 i 的最短距离。
对于 x \in [1, n]，求出 f(x)。
首先，为了最优，我们每次添加的边一定是以 $1$ 为端点。（这很显然）
对于添加长度为 $x$ 的边，判断 $f(y) \leq ans$。如果 $dep_y \leq ans$，那么不需要添加边；否则，添加一条 $1$ 到以这个点为最长链上的中点的边。如果路径长度依旧 $>ans$ 则不合法。
我们每次只需要判断最长链（符合要求的直径）是否合法就可以了。证明：如果有另外一条链它的端点深度 $> ans$，且经最长链的中点到根节点距离 $>ans$，那么它就超过要比最长链还长。
代码：
```cpp
#include <bits/stdc++.h>
#define SZ(x) (int)x.size() - 1
#define all(x) x.begin(), x.end()
#define F(i, a, b) for (int i = (a); i <= (b); i++)
#define DF(i, a, b) for (int i = (a); i >= (b); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> inline void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> inline void chkmin(T &x, T y) {x = min(x, y); }
template <typename T> inline void read(T &x) {
x = 0; int f = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
x *= f;
}
const int N = 3e5 + 10;
vector <int> v[N];
int dep[N], maxn[N];
int dfs(int x, int fa) {
if (x != 1) dep[x] = dep[fa] + 1;
int max1 = dep[x], max2 = dep[x];
for (int i: v[x])
if (i != fa) {
int k = dfs(i, x);
if (k > max1) max2 = max1, max1 = k;
else chkmax(max2, k);
}
int t = min(max1, max2) - 1;
if (t >= 0) chkmax(maxn[t], max1 + max2 - 2 * dep[x] + 1);
return max1;
}
signed main() {
int _; read(_);
while (_--) {
int n; read(n);
F(i, 0, n) v[i].clear(), maxn[i] = 0;
F(i, 2, n) {
int x, y; read(x); read(y);
v[x].push_back(y);
v[y].push_back(x);
}
int k = dfs(1, 0);
DF(i, k - 1, 0) chkmax(maxn[i], maxn[i + 1]);
int ans = 0;
F(i, 1, n) {
while (ans < k && maxn[ans] / 2 + i > ans) ans++;
cout << ans << " ";
} cout << endl;
}
return 0;
}
```