二刷提高课，题解目录在这里— 提高课的题解目录

原来只知道这种求法可以求出有关树的直径的一些问题
二刷后才知道原来这就叫做换根DP，使用两边dfs
一次dfs统计子树内的节点对当前节点的贡献
一次dfs统计父亲节点对当前节点的贡献并合并统计最终答案
从而实现将所有节点作为根节点的情况故称为换根DP
最重要的是要掌握这种方法，将其适用于不同场合
注意这种换根DP肯定有一个顶点是无法向上询问的（1节点）
但是没有影响，只要我们确保将其所有边都计算到即可
若想仔细了解一下可以看这个 树的三大核心

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace  std;
const int N=1e4+10,M=2*N;
int h[N],de[M],ne[M],w[M];
int d1[N],d2[N],p[N],up[N];
int n,dix,res=0x3f3f3f3f;
void add(int a,int b,int c)
{
    de[dix]=b,ne[dix]=h[a],h[a]=dix,w[dix++]=c;
}
int dfs_d(int u,int f)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int j=de[i];
        if(j==f)continue;
        int t=dfs_d(j,u)+w[i];
        if(t>d1[u])
        {
            d2[u]=d1[u],d1[u]=t,p[u]=j;
        }
        else if(t>d2[u])d2[u]=t;
    }
    return d1[u];
}//dfs_d的过程，在遍历子节点时递归再回溯后操作
void dfs_u(int u,int f)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int j=de[i];
        if(j==f)continue;
        if(p[u]!=j)up[j]=w[i]+d1[u];
        else up[j]=w[i]+d2[u];
        up[j]=max(up[j],up[u]+w[i]);
        dfs_u(j,u);
    }
}//记住dfs_u的过程，在遍历子节点时先操作再递归
int main()
{
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    dfs_d(1,-1);
    dfs_u(1,-1);
    for(int i=1;i<=n;i++)
    {
        int a[3];
        a[0]=d1[i],a[1]=d2[i],a[2]=up[i];
        sort(a,a+3);
        res=min(res,a[2]);
    }
    cout<<res;
    return 0;
}