Computer HDU - 2196 (树形dp)

题目来源：Computer

题意

给定一棵有n个节点的树，根的编号为1，求每个点到离它最远的点的距离。

思路

先dfs求出每个点u向下的最大距离f[u][0]和次大距离f[u][1]，并且用数组node[u]记录最大路经过了与u直接相邻的哪一个子节点。

现在用f[u][2]记录满足题意的最大路。

再跑一边dfs，对于当前节点u，如果它的子节点v，满足了node[u] = v，说明u的最大路经过了v，v一定不能通过u的最大路来更新答案，只能通过u的次大路，u的次大路一定不会经过v，即f[v][2] = max(f[u][2], f[u][1]) + u到v的边权；如果不满足，那么v就可以通过u的最大路来更新答案，即f[v][2] = max(f[u][2], f[u][0]) + u到v的边权。

最终的答案要取f[i][2]和f[i][0]的最大值。

要建一个有向树，无向树会T。

代码

#include <bits/stdc++.h>
using namespace std;
struct edge
{
    int to, next, w;
}e[10005];
int cnt, head[10005];
void add(int u, int v, int w)
{
    e[++cnt] = { v, head[u], w };
    head[u] = cnt;
}
int n, f[10005][3], node[10005];
void init()
{
    cnt = 0;
    memset(head, -1, sizeof(head));
    memset(f, 0, sizeof(f));
    memset(node, 0, sizeof(node));
}
void dfs(int u)
{
    for (int i = head[u]; ~i; i = e[i].next)
    {
        int v = e[i].to;
        int w = e[i].w;
        dfs(v);
        if (f[u][0] <= f[v][0] + w)
        {
            f[u][1] = f[u][0];
            f[u][0] = f[v][0] + w; node[u] = v;
        }
        else if (f[u][1] < f[v][0] + w)
        {
            f[u][1] = f[v][0] + w;
        }
    }
}
void Dfs(int u)
{
    for (int i = head[u]; ~i; i = e[i].next)
    {
        int v = e[i].to;
        int w = e[i].w;
        if (node[u] == v)
            f[v][2] = max(f[u][2], f[u][1]) + w;
        else
            f[v][2] = max(f[u][2], f[u][0]) + w;
        Dfs(v);
    }
}
namespace IO
{
    inline char nc() {
        static char buf[100000], *p1 = buf, *p2 = buf;
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
    }
    template<typename T>
    inline T read() {
        char ch = nc(); 
        T sum = 0;
        while (!(ch >= '0'&&ch <= '9'))
        {
            ch = nc();
            if (ch == EOF)  return EOF;
        }
        while (ch >= '0'&&ch <= '9')
        {
            sum = sum * 10 + ch - 48;
            ch = nc();
            if (ch == EOF)  return EOF;
        }
        return sum;
    }
}
int main()
{
    while ((n = IO::read<int>())!=EOF)
    {
        init();
        for (int i = 2; i <= n; ++i)
        {
            int u, w;
            u = IO::read<int>();
            w = IO::read<int>();
            add(u, i, w);
        }
        dfs(1);
        Dfs(1);
        for (int i = 1; i <= n; ++i)
            printf("%d\n", max(f[i][2], f[i][0]));
    }
    return 0;
}