树的直径、中心 - 洛谷保存站

T1：【模板】树的中心

$50pts$：直接暴力，枚举根跑$dfs$，时间复杂度$o(n^2)$。

```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,maxx=0,dep[1000001];
struct node{
	int v,w;
};
vector<node>g[1000001];
vector<int>a[1000001];
int ans=1e9;
void dfs(int u,int fa){
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i].v;
		int w=g[u][i].w;
		if(v!=fa){
			dep[v]=dep[u]+w;
			maxx=max(maxx,dep[v]);
			dfs(v,u);
		}
	}
	return;
}
signed main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y,z;
		cin>>x>>y>>z;
		g[x].push_back({y,z});
		g[y].push_back({x,z});
	}
	for(int i=1;i<=n;i++){
		maxx=0;
		dep[i]=0;
		dfs(i,0);
		a[maxx].push_back(i);
		ans=min(ans,maxx);
	}
	for(int i=0;i<a[ans].size();i++){
		cout<<a[ans][i]<<"\n";
	}
	return 0;
}
```

$100pts$：

1.优化暴力中心一定在树的直径上，所以用$dfs$求直径两个端点，分别以两个端点为根，则两个端点到树上其他点的距离就是深度，最后枚举答案根。

```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,maxx=0,pos,s,t,dep[1000001][2],zzj;
struct node{
	int v,w;
};
vector<node>g[1000001];
int a[1000001];
int ans=1e9;
void zj(int u,int fa,int sum){
	if(sum>zzj){
		zzj=sum;
		pos=u;
	}
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i].v,w=g[u][i].w;
		if(v!=fa){
			zj(v,u,sum+w);
		}
	}
	return ;
}
void dfs(int u,int fa,int k){
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i].v;
		int w=g[u][i].w;
		if(v!=fa){
			dep[v][k]=dep[u][k]+w;
			dfs(v,u,k);
		}
	}
	return;
}

signed main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y,z;
		cin>>x>>y>>z;
		g[x].push_back({y,z});
		g[y].push_back({x,z});
	}
    zj(1,0,0);
	zzj=0;
    s=pos;
	zj(s,0,0);
    t=pos;
    dfs(s,0,0);
    dfs(t,0,1);
	for(int i=1;i<=n;i++){
		maxx=max(dep[i][0],dep[i][1]);
		a[i]=maxx;
        ans=min(maxx,ans);
	}
	for(int i=1;i<=n;i++){
		if(ans==a[i]){
            cout<<i<<"\n";
        }
	}
	return 0;
}
```

2.树形dp

通过两次DFS计算每个节点的向下和向上最长路径，从而得到每个节点到其他节点的最长路径。

以$x$为子树节点的最长链可能在子树内部，也有可能在父节点方向。

`dfs1`函数：记录每个节点向下的最长（`down1`）和次长（`down2`）路径，并记录`son`数组。

`dfs2`函数：记录每个节点向上的最长路。

如果`v`是`u`的最长路径上的子节点（即`son[u] == v`），则`v`的向上路径`up[v]`由`u`的次长向下路径`down2[u]`或`u`的向上路径`up[u]`中的最大值加上边权`w`决定：`up[v] = max(down2[u], up[u]) + w`。

如果`v`不是`u`的最长路径上的子节点，则`v`的向上路径`up[v]`由`u`的最长向下路径`down1[u]`或`u`的向上路径`up[u]`中的最大值加上边权`w`决定：`up[v] = max(down1[u], up[u]) + w`。

```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int n,down1[maxn],down2[maxn],up[maxn],son[maxn];
struct node{
	int v,w;
};
vector<node>g[maxn];
void dfs1(int u,int fa){
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i].v;
		int w=g[u][i].w;
		if(v!=fa){
			dfs1(v,u);
			int tmp=down1[v]+w;
			if(down1[u]<tmp){
				down2[u]=down1[u];
				down1[u]=tmp;
				son[u]=v;
			}else if(down2[u]<tmp){
				down2[u]=tmp;
			}
			
		}
	}
	return;
}
void dfs2(int u,int fa){
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i].v;
		int w=g[u][i].w;
		if(v!=fa){
			if(son[u]==v){
				up[v]=max(down2[u],up[u])+w;
			}else{
				up[v]=max(down1[u],up[u])+w;
			}
			dfs2(v,u);
		}
	}
	return;
}
int main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y,z;
		cin>>x>>y>>z;
		g[x].push_back({y,z});
		g[y].push_back({x,z});
	}
	
	dfs1(1,0);
	dfs2(1,0);
	int res=INT_MAX;
	for(int i=1;i<=n;i++){
		res=min(res,max(down1[i],up[i]));
	} 
	for(int i=1;i<=n;i++){
		if(max(down1[i],up[i])==res){
			cout<<i<<"\n";
		}
	} 
	return 0;
}
```

正在渲染内容...