树的直径、重心、中心
一、树的直径
我们将一棵树 \(T=(V,E)\) 的直径定义为 $max(u,v)(u,v∈V) $，即树中所有最短路径距离的最大值即为树的直径。
求法：
1）树形dp
定义d1为从节点u到其子树中节点距离的最大值,d2为次大值,则\(diameter=max(d1+d2)\)
特点：不可输出路径，但可以处理负边权的树
inline int dfs(int u,int f){
int d1=0,d2=0,d;
for(auto k:g[u]){
int v=k.first,w=k.second;
if(v==f) continue;
d=dfs(v,u)+w;
if(d>d1) d2=d1,d1=d;
else if(d>d2) d2=d;
}
ans=max(ans,d1+d2);
return d1;
}
另一种写法（感觉比较少见）
定义dp[u]为以u到其子树内节点的最远距离,则待选的一条直径可以表示为两条这样的链长之和（其实就是次长链和长链），在用本次的dp[v]去更新dp[u]之前,二者一定是两条不同的链，可以很方便地更新答案
inline void dfs(int u,int f){
for(int i=first[u];i;i=e[i].ne){
int v=e[i].v,w=e[i].w; if(v==f) continue;
dfs(v,u);
ans=max(ans,d[u]+d[v]+w);//ans即为所求
d[u]=max(d[u],d[v]+w);
}
}
2）两次dfs
第1次dfs从任意点出发，到达的离它最远点一定是树的直径的一个端点（具体证明参见），将其记为p
第2次dfs从点p出发,到达的最远点一定是树的直径的另一个端点，所以记录d[i]为从起点到i的路径长度,则最终的d[p]即为树的直径的长度
特点：记录每个点的前驱pre[i]后可以输出树的一条直径上的所有点，但不能处理负边权的树（参见证明）
inline void dfs(int u,int f){
pre[u]=f;
if(d[u]>d[p]) p=u;
for(int i=first[u];i;i=e[i].ne){
int v=e[i].v,w=e[i].w;
if(v==f) continue;
d[v]=d[u]+w;
dfs(v,u);
}
}
int main(){
int u,v,w;
scanf("%d",&n); F(i,1,n-1){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w); add(v,u,w);
}
dfs(1,0); d[p]=0;
dfs(p,0); int x=p; while(pre[x]) printf("%d->",x),x=pre[x]; printf("%d\n",x);//直径具体路径
printf("%d",d[p]);//直径长度
return 0;
}
二、树的重心
在一棵树上，若删去节点u后得到的最大连通块（又叫最大独立集）的点数最小，则u是这棵树的重心
性质1：一棵树最多有两个重心
性质2：去掉重心后最大独立集大小不超过n/2
性质3：重心到树上各点的距离和最小，即能使\(\sum_{i∈V} dis(i,u)\)最小化
用树形DP求解，时间复杂度\(O(N)\)
inline void dfs(int u,int f){
sz[u]=1; int maxn=0;
for(int i=first[u];i;i=e[i].ne){
int v=e[i].v; if(v==f) continue;
dfs(v,u);
sz[u]+=sz[v];
if(sz[v]>maxn) maxn=sz[v];
}
maxn=max(maxn,n-sz[u]);
if(maxn<mn) ans[cnt=1]=u,mn=maxn;
else if(maxn==mn) ans[++cnt]=u;
}
另一种写法，用性质2
inline void dfs(int u,int f){
bool chk=1; int mx=-1;
sz[u]=1; for(int i=first[u];i;i=e[i].ne ){
int v=e[i].v; if(v==f) continue;
dfs(v,u); sz[u]+=sz[v]; mx=max(sz[v],mx);
if(sz[v]>n/2) chk=0;
}
if(n-sz[u]>n/2) chk=0;
if(chk) zx[++cnt]=u,ans=max(mx,n-sz[u]);
}
应用1：洛谷P1395 会议
求图上一点u，使\(\sum_{i∈V} dis(i,u)\)最小化
解法1：用性质3，当断掉u后树的形态尽量均衡（或者说平衡）时结果一定最小，即求树的重心，然后在以以之为根dfs一遍求出dis即可
解法2：树形DP，记\(dp_u\)表示在u点开会的距离之和，则有转移方程：
最后对dp取min即可
三、树的中心
到树上各点的最大距离最小，即\(max_{i∈V}dis(i,u)\)最小的节点是树的中心
性质1：树的中心一定在树的直径上
性质2：一棵树最多有2个中心
求法：
1）延续树的直径的dp做法，记录d1,d2,up分别表示向下走的最大值，次大值，向上走的最大值。
对于d1,d2：同树的直径
对于up：如果v在u的向下最大链上，那就用d2[u]更新up[v]，否则用d1[u]
inline void dfsdown(int u,int f){
int d;
for(int i=first[u];i;i=e[i].ne){
int v=e[i].v,w=e[i].w; if(v==f) continue;
dfsdown(v,u);
d=d1[v]+w;
if(d>d1[u]) d2[u]=d1[u],d1[u]=d,p[u]=v;//记录v在u的最长链上
else d2[u]=d;
}
}
inline void dfsup(int u,int f){
for(int i=first[u];i;i=e[i].ne){
int v=e[i].v,w=e[i].w; if(v==f) continue;
if(p[u]==v) up[v]=max(up[u],d2[u])+w;
else up[v]=max(up[u],d1[u])+w;
dfsup(v,u);
}
}
int main(){
scanf("%d",&n); int u,v,w;
// mem(d1),mem(d2),mem(up);
F(i,1,n-1){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w); add(v,u,w);
}
dfsdown(1,0);
dfsup(1,0);
F(i,1,n){
int z=max(d1[i],up[i]);//z即节点i与其他节点的最远距离
if(z<dis) zx[cnt=1]=i,dis=z;//最小化最远距离的点即为树的中心
else if(z==dis) zx[++cnt]=i;
}
printf("%d %d\n",cnt,dis);
F(i,1,cnt) printf("%d ",zx[i]);
return 0;
}
2）用性质1，先找出直径，然后统计出直径上每一点到两端点的距离最后取min即为树的中点
inline void dfs(int u,int f){
pre[u]=f;
if(d[u]>d[p]) p=u;
for(int i=first[u];i;i=e[i].ne){
int v=e[i].v,w=e[i].w;
if(v==f) continue;
d[v]=d[u]+w;
dfs(v,u);
}
}
inline void dfs2(int u,int f){
// if(u!=st) printf("%d=>",u);//输出直径
int z=max(dis,d[u]);
if(z<mn) mn=z,zx[cnt=1]=u;
else if(z==mn) zx[++cnt]=u;
for(int i=first[u];i;i=e[i].ne){
int v=e[i].v,w=e[i].w; if(v==f || v!=pre[u]) continue;
dis+=w; dfs2(v,u);
}
}
int main(){
int u,v,w;
scanf("%d",&n); F(i,1,n-1){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w); add(v,u,w);
}
dfs(1,0); d[p]=0;
dfs(p,0); st=p;
dfs2(p,0);
// printf("%d\n",st);//输出直径
printf("%d %d\n",cnt,mn);
F(i,1,cnt) printf("%d ",zx[i]);
return 0;
}