首页 > > 程序设计 > C/C++ >

HDU2196 Computer(树形DP)

2018-06-17 20:26:30来源：未知阅读 ()

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 32795 Accepted Submission(s): 4689

Problem Description

A school bought the first computer some time ago(so this computer's id is 1). During the recent years the school bought N-1 new computers. Each new computer was connected to one of settled earlier. Managers of school are anxious about slow functioning of the net and want to know the maximum distance Si for which i-th computer needs to send signal (i.e. length of cable to the most distant computer). You need to provide this information.

Hint: the example input is corresponding to this graph. And from the graph, you can see that the computer 4 is farthest one from 1, so S1 = 3. Computer 4 and 5 are the farthest ones from 2, so S2 = 2. Computer 5 is the farthest one from 3, so S3 = 3. we also get S4 = 4, S5 = 4.

Input

Input file contains multiple test cases.In each case there is natural number N (N<=10000) in the first line, followed by (N-1) lines with descriptions of computers. i-th line contains two natural numbers - number of computer, to which i-th computer is connected and length of cable used for connection. Total length of cable does not exceed 10^9. Numbers in lines of input are separated by a space.

Output

For each case output N lines. i-th line must contain number Si for i-th computer (1<=i<=N).

Sample Input

5 1 1 2 1 3 1 1 1

Sample Output

3 2 3 4 4

Author

scnu

Recommend

lcy | We have carefully selected several similar problems for you: 1561 1011 3456 1520 2242

题目大意：

给出一棵树，问从每个点出发所能到达的最远距离

Sol：

对于一个点，从它出发能到达的最远的距离有两种情况：

1.从它出发到子树内某个点的最长距离

2.从它的父亲边开始走能走到的最远距离

对于第一种情况，我们在转移的时候先遍历一个节点的儿子，然后在每个儿子能到达的最远距离+这条边的权值中取最大值更新

对于第二种情况，我们需要分类讨论：

如果该点是父亲的最长的儿子，那么我们需要从它的父亲所能到达的距离次大的儿子和父亲向上走能到达的最远距离中取max

如果该点不是父亲的最长儿子，那么我们需要从它的父亲所能到达的距离最大的儿子和父亲向上走能到达的最远距离中取max

因此对于一个点，我们需要维护三个量：子树中距离最大的儿子，子树中距离次大的儿子，从父边出发能到达的最远距离

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 10001;
struct Edge {
    int u, v, w, nxt;
}E[MAXN << 1];
int head[MAXN], num = 1;
inline void AddEdge(int x, int y, int z) {
    E[num] = (Edge){x, y, z, head[x]};
    head[x] = num++;
}
int N; 
int f[MAXN][3], fa[MAXN], longson[MAXN];// 0：正向最长 1:正向次长 2:反向最长
int dfs1(int x, int _fa) {//求出点x的最长的儿子/次长的儿子 
    fa[x] = _fa;
    for(int i = head[x], v; i != -1; i = E[i].nxt) {
        if((v = E[i].v) == fa[x]) continue;
        dfs1(v, x);
        int val = E[i].w;
        if(f[v][0] + val > f[x][0]) 
            f[x][1] = f[x][0], f[x][0] = f[v][0] + val, longson[x] = v;
        else if(f[v][0] + val > f[x][1])
            f[x][1] = f[v][0] + val;
    }
    return f[x][0];
}
void dfs2(int x) {
    for(int i = head[x], v; i != -1; i = E[i].nxt) {
        if((v = E[i].v) == fa[x]) continue;
        if(v == longson[x]) f[v][2] = max(f[x][2], f[x][1]) + E[i].w;
        else f[v][2] = max(f[x][2], f[x][0]) + E[i].w;
        dfs2(E[i].v);
    }
}
int main() {
#ifdef WIN32
    freopen("a.in", "r", stdin);
#endif
    while(scanf("%d", &N) != EOF) {
        memset(head, -1, sizeof(head)); num = 1;
        memset(f, 0, sizeof(f));
        for(int i = 2; i <= N; i++) {
            int y, z;
            scanf("%d %d", &y, &z);    
            AddEdge(i, y, z); AddEdge(y, i, z);        
        }
        dfs1(1, 0);
        dfs2(1);
        for(int i = 1; i <= N; i++) 
            printf("%d\n", max(f[i][0], f[i][2]));
    }
    return 0;
}