树形DP

AcWing 1072. 树的最长路径

Question

Solution

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e4 + 10, M = 2 * N;

int n;
int h[N], e[M], w[M], next_[M], id;
int ans;


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


// u: 当前节点, father: 当前节点的父节点
int dfs(int u, int father)
{
    // 当前结点往下走的 最大长度 和 次大长度 
    int d1 = 0, d2 = 0; 

    for(int i = h[u]; ~i; i = next_[i])
    {
        int j = e[i];
        // 防止往上走 
        if(j == father) continue;

        int d = dfs(j, u) + w[i];

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

    // 感觉这个 ans 只需要在 最外层递归更新一次即可 
    ans = max(ans, d1 + d2);

    return d1;
}


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);
    }

    // 我们可以任意选取一个点作为根节点, 这样整棵树的拓扑结构被唯一确定下来了
    dfs(1, -1);

    cout << ans << endl;

    return 0;
}