hdu 2196 Computer - BuringStraw

hdu 2196 Computer#

Tree dp, ~~damn difficult~~

Problem#

Given a tree with weighted edges, find the distance from each node to its farthest node.

Input:

? An n

? Next n lines, each line contains two integers j,w, where the ith line represents an edge with weight w from (i+1) to j

~~Why did I put the input here? Because I read it wrong at first...~~

Solution#

First, set 1 (or any other node) as the root.

The farthest distance of a node can be found from its children or its parent.

So, we just need to take the maximum of "the farthest distance from its children" and "the farthest distance from its parent that doesn't pass through it, plus the weight of the edge from its parent to it".

Two passes of dfs, the first pass finds the farthest distance from each node's children and the farthest distance that passes through another child (not the second farthest distance).

The second pass checks which side to go, and then takes the max.

if (path[p] == y) {//the farthest distance from its parent passes through itself
    f[y][2] = max(f[p][2], f[p][1]) + e[i].w;//can go to the parent's longest child except itself
}
else {
    f[y][2] = max(f[p][2], f[p][0]) + e[i].w;//can go to the parent's longest child
}

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's longest child passes through 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) {//the farthest distance from its parent passes through itself
            f[y][2] = max(f[p][2], f[p][1]) + e[i].w;//can go to the parent's longest child except itself
            }
            else {
                f[y][2] = max(f[p][2], f[p][0]) + e[i].w;//can go to the parent's longest child
            }
        }
}

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