算法提高之树的最长路径

• 核心思想：树形dp

  • 枚举路径的中间节点
  • 用f1[i] 表示i的子树到i的最长距离,f2[i]表示次长距离
  • 最终答案就是max(f1[i]+f2[i])
  • 

•   #include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    const int N = 1e4+10,M = N<<1;
    
    int n;
    int h[N],e[M],ne[M],w[M],idx;
    int f1[N],f2[N],res;
    
    void add(int a,int b,int c)
    {
        e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
    }
    void dfs(int u,int father)
    {
        f1[u] = f2[u] = 0;  //当前父节点没有更新过距离
        for(int i=h[u];~i;i=ne[i])
        {
            int j = e[i];
            if(j == father) continue;  //加边的时候双向边 不能往回走
            dfs(j,u);  //递归
            
            //新的值比最长还大 更新次长为原最长 最长为新最长
            if(f1[j] + w[i] >= f1[u]) f2[u] = f1[u] , f1[u] = f1[j] + w[i];
            //先判断上面 再判断下面 只比次长距离长 更新次长
            else if(f1[j] + w[i] > f2[u]) f2[u] = f1[j]+w[i];
        }
        res = max(res,f1[u]+f2[u]);
    }
    int main()
    {
        memset(h, -1, sizeof h);
        cin>>n;
        for(int i=0;i<n-1;i++)
        {
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c),add(b,a,c);
        }
        
        dfs(1,-1);  //随便一个点作根节点
        cout<<res<<endl;
    }