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 the farthest node from it.

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 misread it at first...~~

Solution#

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

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

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

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

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

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