(资料图)

给定一棵树，树中包含 n 个结点（编号1~n）和 n−1条无向边，每条边都有一个权值。请你在树中找到一个点，使得该点到树中其他结点的最远距离最近。

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

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

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

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

2

#include#include#includeusing namespace std;#define int long longconst int N=1e4+5,M=2*N,INF=0x3f3f3f3f;int h[N],e[M],ne[M],w[M],idx;int leaf[N],d1[N],d2[N],up[N],next1[N];void add(int x,int y,int z){e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;}int dfs_down(int u,int f){int dist=0;d1[u]=d2[u]=0;for(int i=h[u];~i;i=ne[i]){int j=e[i];//防止回头if(j==f)continue;//求当前结点向下的路径int dis=dfs_down(j,u)+w[i];//更新该结点向下的最长路径dist=max(dist,dis);//更新最长路径和次长路径if(dis>d1[u])d2[u]=d1[u],d1[u]=dis,next1[u]=j;else if(dis>d2[u])d2[u]=dis;}//如果该结点向下没有边，则说明该结点为叶子结点if(dist==0)leaf[u]=1;return dist;}void dfs_up(int u,int f){for(int i=h[u];~i;i=ne[i]){int j=e[i];if(j==f)continue;//如果u结点向下的最长路径经过了j，//则表示j结点向上的最长路径为u的次长路径和u结点向上的最长路径的最大值加上w[i]if(next1[u]==j)up[j]=max(up[u],d2[u])+w[i];//否则则表示j结点向上的最长路径为u的最长路径和u结点向上的最长路径的最大值加上w[i]else up[j]=max(up[u],d1[u])+w[i];dfs_up(j,u);}} signed main(){int n,x,y,z;cin>>n;memset(h,-1,sizeof h);for(int i=0;i>x>>y>>z;//建立无向边add(x,y,z);add(y,x,z);}//更新向下的最长路径和次长路径长度dfs_down(1,-1);//更新向上的最长路径dfs_up(1,-1);int res=INF;for(int i=1;i<=n;i++){    //如果该结点是叶子结点，则只需要比较向上的最长路径即可if(leaf[i])res=min(res,up[i]);//否则需要比较向上的最长路径和向下的最长路径else res=min(res,max(up[i],d1[i]));}cout<