1073. 树的中心（树形dp）

大致题意：求出树上所有点的最远距离的最小值。
解题思路：先找出每个点向下的最大值和最小值并且记录经过最大值的下一个节点编号，最远距离无非就是要么就是向下要么就是向上，向下的值就是d1，而向上的有两种，比如当前点是j上一个点是u,那要先加上u和j之间的距离，然后分情况，一种就是上一个点的向上最大值+这条边，另一种情况就是上一个点向下的最大值+这条边（如果经过j这个点就只能退而求其次找次大值）。两者取一个max，最后再遍历所有点，找出最小的最大距离。

#include<iostream>
#include<cstring>
using namespace std;
const   int N=10010,M=20010;
int h[N],e[M],ne[M],w[M],idx;
int up[N],d1[N],d2[N],p1[N];
const   int INF=-0x3f3f3f3f;
void add(int a,int b,int c)
{
   
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int dfs_d(int u,int fa)
{
   
    d1[u]=INF,d2[u]=INF;
    for(int i=h[u];~i;i=ne[i])
    {
   
        int j=e[i];
        if(j==fa)   continue;
        int d=dfs_d(j,u)+w[i];
        if(d>=d1[u])
        {
   
            d2[u]=d1[u],d1[u]=d,p1[u]=j;
        }
        else if(d>=d2[u])
        {
   
            d2[u]=d;
        }
    }
    if(d1[u]==INF && d2[u]==INF)
    d1[u]=0,d2[u]=0;
    return  d1[u];
}
void dfs_u(int u,int fa)
{
   
    for(int i=h[u];~i;i=ne[i])
    {
   
        int j=e[i];
        if(j==fa)   continue;
        if(p1[u]==j)
        {
   
            up[j]=max(up[u],d2[u])+w[i];
        }
        else
        up[j]=max(up[u],d1[u])+w[i];
        dfs_u(j,u);
    }
}
int main()
{
   
    memset(h,-1,sizeof h);
    int n;
    cin>>n;
    for(int i=0;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);
    int res=0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
   
        res=min(res,max(up[i],d1[i]));
    }
    cout<<res<<endl;
    return 0;
}