学步园

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define maxn 10003

struct E
{
    int v, next, w;
}edge[maxn<<1];

int tot, head[maxn];
int n, m;

void init()
{
    tot = 0;
    memset(head, -1, sizeof(int)*(n+1));
}

void add(int s, int t, int w)
{
    edge[tot].v = t;
    edge[tot].w = w;
    edge[tot].next = head[s];
    head[s] = tot++;
}

int f1[maxn], f2[maxn];
int g1[maxn], g2[maxn];
void dfs1(int u, int pre)
{
    int i;
    f1[u] = f2[u] = 0;
    for(i = head[u]; i != -1; i = edge[i].next)
    {
        int v = edge[i].v;
        if(v == pre) continue;
        int w = edge[i].w;
        dfs1(v, u);
        if(f1[v] + w > f2[u])
        {
            f2[u] = f1[v] + w;
            g2[u] = v;
            if(f1[u] < f2[u])
            {
                swap(f1[u], f2[u]);
                swap(g1[u], g2[u]);
            }
        }
    }
}

void dfs2(int u, int pre)
{
    int i;
    for(i = head[u]; i != -1; i = edge[i].next)
    {
        int v = edge[i].v;
        if(v == pre) continue;
        int w = edge[i].w;
        if(g1[u] == v)
        {
            if(f2[v] < f2[u] + w)
            {
                f2[v] = f2[u] + w;
                g2[v] = u;
                if(f1[v] < f2[v])
                {
                    swap(f1[v], f2[v]);
                    swap(g1[v], g2[v]);
                }
            }
        }
        else
        {
            if(f2[v] < f1[u] + w)
            {
                f2[v] = f1[u] + w;
                g2[v] = u;
                if(f1[v] < f2[v])
                {
                    swap(f1[v], f2[v]);
                    swap(g1[v], g2[v]);
                }
            }
        }
        dfs2(v, u);
    }
}

int main()
{
    int i, j;
    int x, y;
    while( ~scanf("%d", &n))
    {
        init();
        for(i = 2; i <= n; i++)
        {
            scanf("%d%d", &x, &y);
            add(i, x, y);
            add(x, i, y);
        }
        dfs1(1, -1);
        dfs2(1, -1);
        for(i = 1; i <= n; i++)
            printf("%d\n", f1[i]);
    }
    return 0;
}