题目描述

树形dp，实际上就是两次dfs，
从一个点出发找一条最长边，和一条次长边

#include <iostream>
#include <cstring>
using namespace std;

const int N=10010;
int h[N],ne[N*2],e[N*2],idx;
int w[2*N];
int ans;

void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}

int dfs(int u,int fa)
{
    //表示从当前点往下走的最大长度
    int dist=0;
    int d1,d2;
    //最长距离和次长距离
    d1=0;
    d2=0;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        int d=dfs(j,u)+w[i]; 
        dist = max(dist,d);

        //注意此处是大于等于
        if(d>=d1)
        {
            d2=d1;
            d1=d;
        }
        else if(d>d2)
        {
            d2=d;
        }
    }
    ans = max(ans,d1+d2);

    return dist;

}

int main()
{
    int n;
    memset(h,-1,sizeof h);
    cin>>n;
    n--;
    while(n--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }   

    dfs(1,-1);
    cout<<ans;



    return 0;
}

二刷，此题的思路还是从一个点开始，做dfs，记录最长与次长路径

d1，d2分别维护最长与次长路径,d1作为函数返回值，因为对于一个根节点，每次要换他的儿子，找这个儿子下面的最长路与前一个儿子的最长路比较，若更长则更新

还是没发现与dp有何联系

#include <iostream>
#include <cstring>

using namespace std;

const int N=10010;
int h[N],e[N*20],ne[N*2],w[N*2];
int idx;
int n,ans;

void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}

int dfs(int u,int fa)
{
    int d1=0,d2=0;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        //d只是一条边，dist是从该点开始最长的边
        int d=dfs(j,u)+w[i];

        if(d>=d1) d2=d1,d1=d;
        else if(d>d2) d2=d;
    }

    ans=max(ans,d1+d2);
    return d1;
}

int main()
{
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n-1;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    dfs(1,-1);
    cout<<ans;

    return 0;
}

三刷，重新熟悉树形dp的方法

就是容易忘，再总结一次，树形dp好像和dp没什么关系，就是从一个点出发做dfs，把所有点都做一遍，结果取其中的最大值

#include <iostream>
#include <cstring>

using namespace std;

const int N=100010;
int e[N*2],ne[N*2],w[N*2],idx,h[N];

int n,m;
int ans;

void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}

int dfs(int u,int fa)
{
    int dist=0;
    int d1=0,d2=0;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        int d=dfs(j,u)+w[i];

        dist=max(dist,d);
        if(d>=d1) d2=d1,d1=d;
        else if(d>d2) d2=d;
    }

    ans=max(ans,d1+d2);
    return dist;
}

int main()
{
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n-1;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }

    dfs(1,-1);
    cout<<ans;

    return 0;
}