[Acwing] 树的直径 树DP|DFS

前言

之前学LCA就学过了 知道了DFS方法

这次为了了解树DP,滚过来复习

思路

DFS : 我们只需要 从根节点开始跑到能跑到的最远点,再从该点枚举到最远点那么最后一次便是我们的直径

树形DP : 我们记录当 1 1 1为树的根时，每个节点作为子树的根向下，所能延伸的最远距离 d 1 d1 d1，和次远距离 d 2 d2 d2，那么直径就是所有 d 1 + d 2 d1+d2 d1+d2的最大值。

CODE

DFS

#include 
using namespace std;
const int N = 10000 + 10;

int n, c, d[N];
int h[N],w[N*2],e[N*2],ne[N*2],idx;


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 fa)
{

    for(int i = h[u];~i;i=ne[i])
    {
        int v = e[i];
        if (v == fa) continue;
        d[v] = d[u] + w[i];

        if (d[v] > d[c]) c = v;
        dfs(v, u);
    }
}
void solve()
{
    cin>>n;
    memset(h,-1,sizeof h);

    for(int i=1; i>u>>v>>c;
        add(u,v,c);
        add(v,u,c);
    }

    dfs(1,0);
    d[c] = 0 ;
    dfs(c,0);

    cout>n;
    memset(h,-1,sizeof h);

    for(int i=1; i>u>>v>>c;
        add(u,v,c);
        add(v,u,c);
    }
    dfs(1,0);
    cout