树的直径、重心、中心

一、树的直径

我们将一棵树 \(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;
}