『树直径·树形DP』「四校联考」平衡树

题解

题意很简明扼要，在一棵树上删除一条边并添加一条边，使得树的最长链最小。

很显然，删去的边一定在树的最长链上；否则，尽管其他的边如何变小，树的最长链是始终不变的。

因此我们需要枚举最长链上的每一条边，并将其删除；最后统计删去后的最长链是多少。

显然，当一棵树$tree$的最长链删去以后，便会分裂成子树$tree1$和$tree2$；那么最后的直径的长度只有可能是这三种情况的最大值：

1.$tree1$的直径。假设$tree1$中，原来最长链的一段为$root1$.2.$tree2$的直径。假设$tree2$中，原来最长链的一段为$root2$.3.$tree1$的某一个点和$tree2$的某一个点连接的最长链。

其中$root1$和$root2$可以很容易用两边$dfs$或者$bfs$找到。

我们考虑一下如何计算具体的答案：

先以tree1直径的计算方法为例：

我们知道$tree1$的直径一定不经过$root2$。我们可以以$root2$为根跑一边树形DP，令$f[x]$表示以$i$为根的子树中，最能达到的最大深度。显然有：$$f[x]=max(f[y]+1),y\in son(x)$$ 设$Max1[x]$表示以$x$为根的子树中的最长链，也不难得到：$$Max1[x]=max(Max1[y],f[y_1]+f[y_2]+2),y,y_1,y_2\in son(x)$$ 假设$tree1$中的$u$和$tree2$中的v连接，那么情况$1$的答案就是$Max1[u]$,我们很容易根据自己设的定义得知。同理，情况$2$的答案为$Max2[v]$.

现在我们需要考虑情况$3$的答案：显然在连线时，在$tree1$的一部分一定在$tree1$的直径上；在tree2的一部分一定在$tree2$的直径上。显然，取$tree1$直径的一半，$tree2$直径的一半并连线一定是最优的。如果直径是奇数，对半分后直径一定在较长的一遍，所以除以$2$以后需要向上取证。我们具体可以表达为：$$\lceil \frac{Max1[u]}{2}\rceil +\lceil \frac{Max2[v]}{2}\rceil +1$$.

暴力枚举最长链上的每一条边，对上述三种情况的最大值求最小值即可。

这道题综合了直径的两种求法，同时也运用了树形DP和枚举的思想，可能看了题解后思路非常清晰但是不可否认还是很难哒。

时间复杂度：最坏$O(N)$.在数据为一条链是为$O(N)$.

代码也就100行…

代码如下：

#include <bits/stdc++.h> using namespace std; inline int read(void) { int s = 0, w = 1;char c = getchar(); while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar();} while (c >= '0' && c <= '9') s = s*10+c-48, c = getchar(); return w * s; } const int N = 600000; int root1, root2, ans, n, Max; int f[N]; int Max1[N]; int Max2[N]; int deep[N]; vector <int> a[N]; void dfs1(int x,int fa) { deep[x] = deep[fa] + 1; if (deep[x] > Max) Max = deep[x], ans = x; for (int i=0;i<a[x].size();++i) { int y = a[x][i]; if (y == fa) continue; dfs1(y,x); } return; } //求距离起点最远的点 void find_root(void) { Max = 0, ans = 0, deep[1] = 0; dfs1(1,0), root1 = ans; Max = 0, ans = 0, deep[root1] = 0; dfs1(root1, 0), root2 = ans; return; } //得到原始直径的两个端点 void dfs2(int x,int fa) { f[x] = 0; for (int i=0;i<a[x].size();++i) { int y = a[x][i]; if (y == fa) continue; dfs2(y,x); Max1[x] = max(Max1[x], max(f[x]+f[y]+1, Max1[y])); f[x] = max(f[x], f[y]+1); } return; } //以root1为根求每一个点不经过root1的最长链 void dfs3(int x,int fa) { f[x] = 0; for (int i=0;i<a[x].size();++i) { int y = a[x][i]; if (y == fa) continue; dfs3(y,x); Max2[x] = max(Max2[x], max(f[x]+f[y]+1, Max2[y])); f[x] = max(f[x], f[y]+1); } return; } //以第二个点为根不经过root2的最长链 bool dfs4(int x,int fa) { if (x == root2) return 1; for (int i=0;i<a[x].size();++i) { int y = a[x][i]; if (y == fa) continue; if (dfs4(y,x) == 0) continue; int ans1 = max(Max1[y],Max2[x]); int ans2 = (Max1[y]+1>>1)+(Max2[x]+1>>1)+1; ans = min(max(ans1,ans2),ans); return 1; } return 0; } //对直径进行删边操作 int main(void) { freopen("balance.in","r",stdin); freopen("balance.out","w",stdout); n = read(); ans = INT_MAX; for (int i=1;i<n;++i) { int x = read(); int y = read(); a[x].push_back(y); a[y].push_back(x); } find_root(); dfs2(root1, 0); dfs3(root2, 0); ans = INT_MAX; dfs4(root1, 0); printf("%d\n", ans); return 0; }