hdu2196

基本的树形dp，需要dfs三次，第一次求每个点最远的后代，第二次和第三次每个点的孩子分别从左到右和从右到左遍历。

#include <cstdio>

#include <vector>

using namespace std;

#define D(x)

const int MAX_N = (int)(1e4) + ;

int n;

vector <pair<int, int> > edge[MAX_N];

int child[MAX_N];

int father_left[MAX_N];

int father_right[MAX_N];

void dfs_child(int father, int u)

{

    child[u] = ;

    for (int i = ; i < (int)edge[u].size(); i++)

    {

        int v = edge[u][i].first;

        int w = edge[u][i].second;

        if (v != father)

        {

            dfs_child(u, v);

            child[u] = max(child[u], child[v] + w);

        }

    }

}

void dfs_father_left(int father, int u, int up)

{

    father_left[u] = up;

    int temp = ;

    for (int i = ; i < (int)edge[u].size(); i++)

    {

        int v = edge[u][i].first;

        int w = edge[u][i].second;

        if (v != father)

        {

            dfs_father_left(u, v, max(up, temp) + w);

            temp = max(temp, w + child[v]);

        }

    }

}

void dfs_father_right(int father, int u, int up)

{

    father_right[u] = up;

    int temp = ;

    for (int i = (int)edge[u].size() - ; i >= ; i--)

    {

        int v = edge[u][i].first;

        int w = edge[u][i].second;

        if (v != father)

        {

            dfs_father_right(u, v, max(up, temp) + w);

            temp = max(temp, w + child[v]);

        }

    }

}

int main()

{

    while (scanf("%d", &n) != EOF)

    {

        for (int i = ; i <= n; i++)

        {

            edge[i].clear();

        }

        for (int i = ; i <= n; i++)

        {

            int a, b;

            scanf("%d%d", &a, &b);

            edge[i].push_back(make_pair(a, b));

            edge[a].push_back(make_pair(i, b));

        }

        dfs_child(-, );

        dfs_father_left(-, , );

        dfs_father_right(-, , );

        for (int i = ; i <= n; i++)

        {

            D(printf("%d %d %d\n", child[i], father_left[i], father_right[i]));

            printf("%d\n", max(child[i], max(father_left[i], father_right[i])));

        }

    }

    return ;

}