树的中心

树的中心

给定一棵树，树中包含 n 个结点（编号1~n）和 n−1 条无向边，每条边都有一个权值。

请你在树中找到一个点，使得该点到树中其他结点的最远距离最近。

输入格式

第一行包含整数 n。

接下来 n−1 行，每行包含三个整数 ai,bi,ci，表示点 ai 和 bi 之间存在一条权值为 ci 的边。

输出格式

输出一个整数，表示所求点到树中其他结点的最远距离。

数据范围

1≤n≤10000, 1≤ai,bi≤n, −10^5≤ci≤10^5

输入样例：

5 2 1 1 3 2 1 4 3 1 5 1 1

输出样例：

2

分析：

树的中心：树中找到一个点，该点到树中其他结点的最远距离最近。

为求得当前点到树中其他节点的最远距离，有两种遍历方式：

 

#include <iostream> #include <algorithm> using namespace std; const int N = 10000+10; int head[N],nexts[N*2],ver[N*2],edge[N*2]; int tot,INF=0x3f3f3f3f; int down1[N],down2[N],up[N],p[N]; void add(int x,int y,int z){ ver[++tot]=y,edge[tot]=z; nexts[tot]=head[x],head[x]=tot; } //子节点更新父节点 int dfs_down(int x,int father){ down1[x]=down2[x]=-INF; for(int i=head[x];i;i=nexts[i]){ int y=ver[i],z=edge[i]; if(y==father) continue; int d=dfs_down(y,x)+z; if(d>down1[x]){ down2[x]=down1[x],down1[x]=d; p[x]=y; } else if(d>down2[x]) down2[x]=d; } if(down1[x]==-INF&&down2[x]==-INF) down1[x]=down2[x]=0; return down1[x]; } //父节点更新子节点 void dfs_up(int x,int father){ for(int i=head[x];i;i=nexts[i]){ int y=ver[i],z=edge[i]; if(y==father) continue; if(p[x]==y) up[y]=max(up[x],down2[x])+z; else up[y]=max(up[x],down1[x])+z; dfs_up(y,x); } } int main(){ int n; scanf("%d",&n); for(int i=0;i<n;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } dfs_down(1,0); dfs_up(1,0); int res=INF; for(int i=1;i<=n;i++){ res=min(res,max(down1[i],up[i])); } printf("%d",res); return 0; }