hdu 2196 Computer

树形dp,贼鸡儿难

题目

传送门

给你一棵有边权的树,求每个点到离它最远的点的距离

输入:

​ 一个n

​ 接下来n行每行两个整数j,w,其中第i行表示从(i+1)j有一条权值为w的边

为什么我要把输入放在这里,因为我最开始看错了。。。

解法

首先把1(或者其他点)作为根。

一个节点的最远距离就可以从它的儿子里面或者父亲里面找

所以只要取他“儿子里的最远距离”和“他父亲的/不经过他的/儿子里的最远距离,加上他父亲到他的边权”中的最大值

两遍dfs,第一遍求每个节点儿子理的最远距离,和经过另外一个儿子的最远距离(不是第二远距离)。

第二遍判断一下能走哪边,然后取max

if (path[p] == y) {//他爸的最远距离经过了他自己
    f[y][2] = max(f[p][2], f[p][1]) + e[i].w;//能走父亲除了自己外最长的儿子
}
else {
    f[y][2] = max(f[p][2], f[p][0]) + e[i].w;//能走父亲最长的儿子
}

Code

#include <cstdio>
#define max(a, b) ((a) > (b) ? (a) : (b))

const int MAXN = 1e4 + 5;

struct ed {
    int to, nex, w;
    ed (void) {
        to = nex = w = 0;
    }
} e[MAXN << 1];

int head[MAXN], f[MAXN][3], path[MAXN];
int newp, n;

void insert (int p1, int p2, int w) {
    ++newp;
    e[newp].w = w;
    e[newp].to = p2;
    e[newp].nex = head[p1];
    head[p1] = newp;
}

void dfs1 (int p, int fa) {
    for (int i = head[p]; i; i = e[i].nex) {
        int y = e[i].to;
        if (y != fa) {
            dfs1(y, p);
            if (f[p][0] < f[y][0] + e[i].w) {
                f[p][1] = f[p][0];
                f[p][0] = f[y][0] + e[i].w;
                path[p] = y;//p最长的儿子经过了y
            }
            else if (f[p][1] < f[y][0] + e[i].w) {
                f[p][1] = f[y][0] + e[i].w;
            }
        }
    }
}

void dfs2 (int p, int fa) {
    for (int i = head[p]; i; i = e[i].nex) {
        int y = e[i].to;
        if (y != fa) {
        if (path[p] == y) {//他爸的最远距离经过了他自己
            f[y][2] = max(f[p][2], f[p][1]) + e[i].w;//能走父亲除了自己外最长的儿子
            }
            else {
                f[y][2] = max(f[p][2], f[p][0]) + e[i].w;//能走父亲最长的儿子
            }
        }
}

int main (void) {
    while (scanf("%d", &n) != EOF) {
        newp = 0;
        for (int i = 1; i <= (n << 1); ++i) {
            e[i] = ed();
        }
        for (int i = 1; i <= n; ++i) {
            head[i] = 0;
            path[i] = 0;
            f[i][0] = f[i][1] = f[i][2] = 0;
        }
        for (int i = 2; i <= n; ++i) {
            int p2, w;
            scanf("%d%d", &p2, &w);
            insert(i, p2, w);
            insert(p2, i, w);
        }
        dfs1(1, 0);
        dfs2(1, 0);
        for (int i = 1; i <= n; ++i) {
            printf("%d\n", max(f[i][0], f[i][2]));
        }
    }
    return 0;
}