算法提高之树的中心

• 核心思想：树形dp + 换根dp

  • 每个点作为根节点 找其子树的最大距离和父节点的最大距离

  • dfs1：求子树对于当前根节点的最大距离和次大距离

    • 求次大距离原因：如果当前节点是其父节点子树的最大路径上的点，最大距离不能用
    • 

  • dfs2：找父节点以上的最长距离

•   #include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    const int N = 10010,M=N<<1,INF=0x3f3f3f3f;
    
    int n;
    int h[N],e[M],ne[M],w[M],idx;
    int d1[N],d2[N],up[N];
    int s1[N],s2[N];  //s1存该点最大距离从哪个点过来 s2存次大距离...
    
    void add(int a, int b, int c)
    {
        e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    }
    
    void dfs1(int u,int father)
    {
        for(int i=h[u];~i;i=ne[i])
        {
            int j=e[i];
            if(j == father) continue;
            dfs1(j,u);
            if(d1[j] + w[i] >= d1[u])
            {
                d2[u] = d1[u],d1[u] = d1[j]+w[i];
                s2[u] = s1[u],s1[u] = j;
            }
            else if(d1[j] + w[i]> d2[u])
            {
                d2[u] = d1[j]+w[i] , s2[u] = j;
            }
        }
    }
    
    void dfs2(int u,int father)
    {
        for(int i=h[u];~i;i=ne[i])
        {
            int j=e[i];
            if(j==father) continue;
            //如果j为求最大距离时用的点 d1[u]不能用
            if(s1[u] == j) up[j] = w[i] + max(up[u],d2[u]);  
            else up[j] = w[i] + max(up[u],d1[u]);
            dfs2(j,u);
        }
    }
    int main()
    {
        memset(h,-1,sizeof h);
        cin>>n;
        for(int i=1;i<n;i++)
        {
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c) , add(b,a,c);
        }
        
        dfs1(1,-1);
        dfs2(1,-1);
        
        int res=INF;
        for(int i=1;i<=n;i++) res = min(res,max(d1[i],up[i]));
        cout<<res<<endl;
    }