树的直径与重心

本篇博客主要讲解树的直径，树的重心以及动态维护 注：全文中提到 $u,v$ 均为特定的，表示 $u,v$ 有一条边相连 **0.前置知识** 简单树形 $\text{dp}$，$\text{dfs}$，线段树，树链剖分，动态点分治(点分树)，LCT **1.树的直径** **1.0 定义** 给定一棵树， 树中每条边都有一个权值， 树中两点之间的距离定义为连接两点的路径边权之和。 树中最远的两个节点之间的距离被称为树的直径， 连接这两点的路径被称为树的最长链 简单来说，树的直径就是树上一条最长的链的距离 --- 对于树的直径，我们普遍有两种做法 一种是贪心两遍 $\text{dfs}$ 或 $\text{bfs}$,另外一种是树形 $\text{dp}$ **1.1 贪心** 考虑这样的贪心策略 对于树上一个随机的点 $W$, 我们找到离它距离最远的 $P$, 找到离 $\text{P}$ 距离最远的点 $\text{Q}$, $\text{PQ}$ 的距离即为我们要求的直径 为了方便理解这个算法，我们画个图  我们选择 $5$ 号点作为随机点 $\text{W}$ 找到距离它最远的点 $4$ 号点 $\text{P}$ 找到距离 $4$ 号点最远的点 $6$ 号点 $\text{Q}$ $\text{PQ}$ 的距离即为我们要求的直径 --- 那么如何证明这个定理呢？？？ 首先我们进行分类讨论： **1.1.0 $\text{W}$ 点在直径上** 如果 $\text{W}$ 号点在直径上，对于其他与 $\text{W}$ 联通的点 $\text{X,Y}$ $\text{XY}=\text{XW}+\text{WY}<\text{PW}+\text{PQ}-\text{PW}=\text{PQ}$ 所以 $\text{PQ}$ 最大，证毕 **1.1.1 $\text{W}$ 点不在直径上** 如果 $\text{W}$ 点不在直径上，那 $\text{W}$ 点就没有价值了 这是我们用反证法 我们取一条最长链 $\text{AB(AB!=PQ)}$ 接着分类讨论。 **1.1.1.0 $\text{AB}$ 和 $\text{PQ}$ 有交点** 我们设交点为 $\text{C}$。  因为 $\text{Q}$ 距离 $\text{P}$ 最远，所以 $\text{PQ>PC+CA}$ 所以 $\text{CQ>CA}$ 所以 $\text{CQ+CB>AC+CB}$ 所以 $\text{QB>AB}$ （我们找到了一条比最长链还长的链，推出矛盾) 与 $\text{AB}$ 是最长链矛盾 所以 $\text{PQ}$ 是直径 **1.1.1.1 $\text{AB}$ 和 $\text{PQ}$ 无交点** 我们在 $\text{AB}$ 上取一点 $\text{M}$，在 $\text{PQ}$ 上取一点 $\text{N}$，使得 $\text{MN}$ 联通  因为 $\text{Q}$ 距离 $\text{P}$ 最远，所以 $\text{PQ>PB}$ 所以 $\text{NQ>MN+MB}$ 所以 $\text{AM+MN+NQ>AM+MB}$ 所以 $\text{AQ>AB}$ （我们又找到了一条比最长链还长的链，推出矛盾) 与 $\text{AB}$ 是最长链矛盾 所以 $\text{PQ}$ 是直径 **code:** ``` #include<bits/stdc++.h> #define rd(x) x=read() #define N 20005 using namespace std; int n,m; struct E{ int to,nxt,w; }e[N]; int tot; int ans,pos; int head[N],dis[N]; void addEdge(int u,int v,int w){e[++tot].nxt=head[u],e[tot].to=v,e[tot].w=w,head[u]=tot;} inline int read() { int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void write(int x) { if(x<0){putchar('-');x=-x;} if(x>=10)write(x/10); putchar(x%10+'0'); } void dfs(int u,int fa) { if(ans<dis[u])ans=dis[u],pos=u; for(int i=head[u];i;i=e[i].nxt) { int v=e[i].to; if(v==fa)continue; dis[v]=dis[u]+e[i].w; dfs(v,u); } } int main() { rd(n); for(int i=1;i<=n-1;i++) { int u,v; rd(u),rd(v); addEdge(u,v,1); addEdge(v,u,1); } dis[1]=0,dfs(1,0); ans=0,dis[pos]=0,dfs(pos,0); cout<<ans<<endl; return 0; } ``` --- 因为在贪心的证明中，我们依赖于：$x+y>x(y \in R^+)$ **所以使用两遍 $\text{dfs}$ 或 $\text{bfs}$ 的时候，我们要保证边权为正。** 我们已经证明了贪心的正确性，现在考虑 $\text{dp}$ **1.2 树形 $\text{dp}$** 我们考虑用 $f[i]$ 以 $i$ 为根的子树中和从 $i$ 出发的最长长度 考虑以 $u$ 为根的子树 $f[u]=max(f[u],f[v]+e[i].w)$ 最长长度就是两条链的和 或者说，我们原来找到了一条 $f[u]$ 的链 现在我们新找到了一条由 $v$ 节点继承的链 这两条链长度之和的最大值即为 $ans$ 所以 $ans=max(ans,f[u]+f[v]+e[i].w)$ 注意这句话要写在 $f[u]$ 的转移之前 **code:** ``` void dfs(int u,int fa) { f[u]=0; for(int i=head[u];~i;i=e[i].nxt) { int v=e[i].to; if(v==fa)continue; dfs(v,u); ans=max(ans,f[u]+f[v]+e[i].w); f[u]=max(f[u],f[v]+e[i].w); } } ``` 因为树形 $\text{dp}$ 的做法不需要依赖于 $x+y>x(y \in R^+)$ 的性质，所以边权可以为负 **1.3 树的直径动态维护** 举个例子： 我们需要支持这样的操作：动态查询任意一个子树的直径长度，以及删除一个子树 考虑到每一个子树在 $\text{DFS}$ 序上都是连续的区间，我们可以先搞出整棵树的 $\text{DFS}$ 序，在 $\text{DFS}$ 序上进行操作。 每当我们要查询一个子树的直径长度时，可以使用线段树维护DFS序。 当我们要删除一个在 $\text{DFS}$ 序上连续的区间时，考虑把两个区间进行合并， 左边区间有两个直径端点，右边也有两个，该怎么合并呢？ 我们可以利用一个直径的性质，即两个连通块进行合并的时候，就是两个连通块直径的端点（共计四个点）的最远点对。 怎么证明呢 --- 假设现在有两个需要合并的连通块（如下图）  其中 $1-2-3-5$ 是一个连通块记作 $A$，$4-6-7$是一个连通块记作$B$ 我们要将这两个连通块通过 $1-4$ 联通。 已知 $A$ 连通块内直径长度 $L1$，$B$ 连通块内直径长度 $L2$ 我们假设直径不通过 $1-4$，那么最终的长度 $L=max(L1,L2)$，证毕 如果直径通过 $1-4$ ，由前文性质得知，直径的左右端点分别为$1$和$4$在左右子树中能走到最远的点，也符合我们的性质 **注：前文的性质要求边权为正数，所以在这合并两个连通块的时候，我们依旧要求边权为正** 这个性质用途非常广泛，因为我们可以将**点当成一个连通块对待**，在很多题目中都有体现 --- 所以线段树维护点对和长度即可 在合并的时候，我们要快速求出两个点之间的距离，需要使用 $\text{LCA}$ 进行计算 时间复杂度为 $O(nlog^2n)$ 可以使用 $\text{RMQ}$ 算法优化 $\text{LCA}$，达到查询 $O(1)$，总体时间 $O(nlogn)$ --- 再举个例子，要求支持动态加边，维护直径 简单分析，发现 $\text{LCT}$ 是一个最好的办法， 我们通过可以上文直径的性质，用并查集维护需要加边的点， 用 $\text{LCT}$ 维护直径的左右端点 在添加一条 $u->v$ 的边时，找出 $u,v$ 的祖先 $fx,fy$，算出两边的直径 由于最终的直径端点只可能是 $l[fx],l[fy],r[fx],r[fy]$ 中的一个，暴力枚举即可。 时间复杂度 $O(nlogn)$，只不过常数有点大，大概是6倍左右，还要加上LCT的常数 --- 上面介绍了两种不同的思想，一种是线段树维护DFS序，一种是LCT直接维护， 但是都用到了树的直径的性质，请大家牢记这个性质。 --- **2.树的重心** 考虑一个点，以它为根的树中，最大的子树节点数最少，我们把这个点称为树的重心 举个例子，下图中重心为 $1$ 和 $2$  **2.0 树形dp求重心** 求解树的重心的时候，我们通常会采用树形 $\text{dp}$ 我们用 $s[i]$ 代表以 $i$ 为根的子树节点数 $f[i]$ 代表以 $i$ 为根的子树中最大的子树节点个数 显然，$f[u]=max(f[u],s[v])$ 但是我们求重心的时候，**是以 $u$ 为根**。 还是举上图的例子，当我们把2号点当成重心时，它就变成了这样  这时候 $2$ 号节点的~~父亲变成了儿子~~ 所以最后统计 $f[u]$ 的时候，还要记得统计 $n-s[u]$ (即以原来父亲为根的子树的节点数) **code:** ``` void dfs(int u,int fa) { s[u]=1,f[u]=0; for(int i=head[u];i;i=e[i].nxt) { int v=e[i].to; if(v==fa)continue; dfs(v,u); s[u]+=s[v]; f[u]=max(f[u],s[v]); } f[u]=max(f[u],n-s[u]); } ``` 如果题目让我们求多个重心的编号，在最后统计的时候注意一下即可 **code:** ``` #include<bits/stdc++.h> #define rd(x) x=read() #define N 20005 using namespace std; int n,m; struct E{ int to,nxt; }e[N]; int tot; int ans,pos; int head[N]; int f[N],s[N]; void addEdge(int u,int v){e[++tot].nxt=head[u],e[tot].to=v,head[u]=tot;} inline int read() { int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void write(int x) { if(x<0){putchar('-');x=-x;} if(x>=10)write(x/10); putchar(x%10+'0'); } void dfs(int u,int fa) { s[u]=1,f[u]=0; for(int i=head[u];i;i=e[i].nxt) { int v=e[i].to; if(v==fa)continue; dfs(v,u); s[u]+=s[v]; f[u]=max(f[u],s[v]); } f[u]=max(f[u],n-s[u]); } int main() { rd(n); for(int i=1;i<=n-1;i++) { int u,v; rd(u),rd(v); addEdge(u,v); addEdge(v,u); } dfs(1,-1); int minn=1e9; for(int i=1;i<=n;i++)minn=min(minn,f[i]); for(int i=1;i<=n;i++)if(f[i]==minn)printf("%d ",i); printf("\n"); return 0; } ``` --- **2.1 一些性质** 树的重心有一堆~~稀奇古怪~~好玩的性质 但是一堆终究还是一个 **2.1.0 第一个性质** 把它摆在第一个，也代表它是最重要的性质 考虑上图中的 $2$ 号点 它的子树中节点个数最大的子树是以 $1$ 号点为根的子树 我们考虑以 $1$ 号点为根的子树的根节点，把它作为我们假想的重心，我们把它称为**伪重心**（为了方便说明，这个名词是我造的） 伪重心的子树显然是不平衡的 当我们取伪重心作为重心的时候 设以伪重心为根的子树的节点个数（即原重心最大子树的节点个数）为 $x$,原重心其他子树的节点数之和为 $y$ 以伪重心为根，有两棵子树，一颗为 $x-1$，一颗为 $y+1$ 我们要保证重心是最优的 所以 $x-1<[(n-1)/2]$ $x<=[n/2]$ 这就是第一个性质: **以重心为根，所有的子树的大小都不超过整个树大小的一半。** **2.1.1 树的重心最多有两个。** 当一棵树有两个重心时，为了保持尽量平衡，它的第二个重心肯定在以第一个重心为根的最大的子树根节点上。 根据性质1中的证明：当 $x=[n/2]$ 时，这颗树就有两个重心。 **2.1.2 树的重心到其他节点的距离是最小的** 注：相邻两个节点距离为 $1$. 每一次我们一格一格的从重心移动。 假设我们将重心向一棵子树移动，设那颗子树的节点数为 $s$ 每移动一格，树的根节点就变化一次。 对于每一次移动，设上一次重心为 $u$ 当前重心为 $v$ 设$v$的子树节点数为 $s[v]$ $v$ 的子树的每个节点距离重心减少 $1$ 其他的所有节点距离重心增加 $1$ 设 $ans[u]$ 表示 $u$ 到其他节点的距离 则 $ans[u]=ans[v]+n-s[v]-s[v]=ans[v]+n-2*s[v]$ 因为对于重心的每一个节点 $s[i]<=[n/2]$ 所以重心到其他节点的距离是最小的。 用上面那个递推式还可以求出距离其他节点最远的节点 **2.1.3 把两个树通过一条边相连得到一个新的树，那么新的树的重心在连接原来两个树的重心的路径上。** 关于这一点的证明较为感性 我们考虑以两棵树的重心为根，即以重心把整棵树提起来。 当我们用一条边把两棵树 $\text{A,B}$ 连接起来时， 我们先考虑树 $\text{A}$ 对于树 $\text{A}$, 我们可以理解为树 $\text{A}$ 中的一个节点拥有了所有树$B$的节点 那么整体的中心肯定偏向那一侧 对于树 $\text{B}$，我们也可以这么理解 所以在偏向的过程中，中心可能存在的位置一定在树 $\text{A}$ 重心和树 $\text{B}$ 重心的连线上 **2.1.4 把一个树添加或删除一个叶子，那么它的重心最多只移动一条边的距离。** 这个请读者利用以上性质自行证明 ---- **2.2 树的重心动态维护** 考虑添加，删除，移动一片叶子 这三种操作在[fanhq666的博客](http://fanhq666.blog.163.com/blog/static/81943426201172472943638) 都有简单的说明 可惜原博客的链接挂了，这里有个新的[链接](https://www.cnblogs.com/qlky/p/5781081.html) 而我们关注的，是更加详细的做法 注意到 fhq 大爷的博客里有这么一句话 > 定义稍微广义的树的重心：每个点有一个非负权，每个边有个正的长度，到所有点的权乘以距离的和最小的点定义为重心。 我们先不考虑移动一片叶子，对于添加一片叶子，就是把一片叶子的点权改为1，删除一片叶子，就是把一片叶子的点权改为 $0$ 考虑假设我们要维护广义中心的点权（加减一个值）， 如果我们解决了上面这个问题，我们就可以维护添加和删除了 动态点分治（点分树）固然可做，这里提供一种树链剖分的方法. **即使我们把重心的定义广义化了，** **重心依旧不依赖于边权** 回顾一下原定义： > **考虑一个点，以它为根的树中，最大的子树节点数最少，我们把这个点称为树的重心** 这里，我们要把节点数改为节点权值总和 这里证明一下： 我们用类似证明性质 $2.1.2$ 的方法，考虑从重心移动一次 我们用 $w(u,v)$ 表示 $u->v$ 的距离, $e(u)$ 表示 $u$ 的点权, $f(u)$ 表示总和 定义 $f(u)=\sum e(v)*w(u,v)$ 因为这是一颗无根树，所以我们以最大的子树节点权值总和最小的点 $u$ 为根, $size_i$ 表示 $u$ 节点的第 $i$ 个子树的大小，$s_i$ 表示 $size_i$ 表示 $u$ 节点的第 $i$ 个子树 移动一条边之后，设$u'$是$u$的第$k$个子树的根节点， $f(u')=f(u)-\sum e(v)(v \in s_i)+\sum e(v)(v \notin s_i)$ 因为保证了 $\sum e(v)(v \in s_i)<=[\sum e(v)/2]$ 所以 $f(u')>=f(u) $ 所以 $f(u)$ 是最优的。 --- 因为一条链上深度越大 $\text{dfs}$ 序越大， 所以根据这个性质，我们只要找到一个点 $u$ , 使得 $f(u)*2>=f(rt)$，且 $u$ 节点最深 这个可以在线段树上利用二分快速找出。 我们用 $cost$ 表示花费，$e(v),w(u,v)$ 的定义同上 $cost=\sum e(v)*w(u,v)$ 对于 $w(u,v)$ 我们可以用LCA维护： $w(u,v)=w(u,rt)+w(v,rt)-2*w(lca,rt)$ 则原式可化为： $cost=\sum w(u,rt)*e(v)+\sum w(v,rt)*e(v)-2*w(lca,rt)*e(v)$ 在更新的时候，记录一下 $\sum \Delta e$ 和 $\sum \Delta w(u,rt)*e$即可，时间复杂度 $O(1)$ 对于 $w(lca,rt)*e(v)$ 每一次更新时，我们都从当前节点到根节点的大小$size$一路修改 查询时，即查询 $\sum (w(u,rt)-w(fa[u],rt))*size(u)$ $w(u,rt)-w(fa[u],rt)$ 用线段树维护即可 时间复杂度 $O(nlog^2n)$ **3.相关文献** 参考文献： 1.[YuWenjue的博客](https://www.cnblogs.com/ywjblog/p/9254997.html) 2.[forever_dreams的博客](https://blog.csdn.net/forever_dreams/article/details/81051578) 3.[fanhq666的博客](http://fanhq666.blog.163.com/blog/static/81943426201172472943638) 4.[kai586123的博客](https://kai586123.blog.luogu.org/solution-p3345) **4.后记** ~完结撒花~