树的中心

从树的直径我们可以知道 任意一个点离自己最远的点一定是直径端点中的一个
那么最大距离最小的一定是与直径2个端点距离中取最大值中的最小值
在我看来我的代码比y总的2个dfs看上去更舒服
话不多说 直接上代码

#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
#define N 10010
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
struct  Edge{
    int next,v,w;
}edge[N<<1];
int head[N],tot=0,dis[N];
void adde(int u,int v,int w){
    edge[++tot].next=head[u];
    edge[tot].v=v;
    edge[tot].w=w;
    head[u]=tot;
}
void dfs(int u,int fa,int cnt){
    dis[u]=max(cnt,dis[u]);//以x，y为根进行2次dfs可以用来求任意一点与自己最远的点的距离
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].v;
        int w=edge[i].w;
        if(v!=fa)
        dfs(v,u,cnt+w);
    }
}
int main(){
    int n=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read(),w=read();
        adde(u,v,w);
        adde(v,u,w);
    }
    dfs(1,1,0);
    int res=0,x,y;
    for(int i=1;i<=n;i++){
        if(res<dis[i]){//找出端点x
            res=dis[i];
            x=i;
        }
    }
    memset(dis,0,sizeof(dis));//将先前的清0
    dfs(x,x,0);
    res=0;
    for(int i=1;i<=n;i++){//找出端点y
        if(res<dis[i]){
            res=dis[i];
            y=i;
        }
    }
    dfs(y,y,0);//以y为起点在搜索一起
    res=0x3f3f3f3f;
    for(int i=1;i<=n;i++){
        res=min(res,dis[i]);
    }
    cout<<res;
}