随笔档案

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define inf (1<<29)
const int maxn = 10010;
vector <pair<int,int> > G[maxn];
int node1[maxn],node2[maxn];
int dis1[maxn],dis2[maxn],dis3[maxn];
int p[maxn];
int n;
void init() {
    for(int i=1;i<=n;i++) {
        G[i].clear();
        node1[i] = node2[i] = -1;
        dis1[i] = dis2[i] = dis3[i] = 0; 
        p[i] = -1;
    }   
}
int dfs1(int u) {
    if(dis1[u]) return dis1[u];
    int sz = G[u].size();
    for(int i=0;i<sz;i++) {
        int v = G[u][i].first , w = G[u][i].second;
        if(v == p[u]) continue;
        p[v] = u;
        if(dfs1(v) + w > dis1[u]) dis1[u] = dis1[node1[u] = v] + w;
    }
    for(int i=0;i<sz;i++) {
        int v = G[u][i].first , w = G[u][i].second;
        if(v == p[u] || v == node1[u]) continue;
        if(dis1[v] + w > dis2[u]) dis2[u] = dis1[v] + w;
    }
    return dis1[u];
}
void dfs2(int u) {
    int sz = G[u].size();
    for(int i=0;i<sz;i++) {
        int v = G[u][i].first , w = G[u][i].second; 
        if(v == p[u]) continue;    
        dis3[v] = dis3[u] + w;
        if(v == node1[u])
            dis3[v] = max(dis3[v],dis2[u]+w);
        else
            dis3[v] = max(dis3[v],dis1[u]+w);
        dfs2(v);
    }
}
int main() {
    while(~scanf("%d",&n)) {
        init();
        int a , b;
        for(int i=2;i<=n;i++) {
            scanf("%d%d",&a,&b);
            G[i].push_back(make_pair(a,b));
            G[a].push_back(make_pair(i,b));
        }   
        dfs1(1);
        dfs2(1);
        for(int i=1;i<=n;i++) {
            printf("%d\n",max(dis1[i],dis3[i]));   
        }
    }
    return 0;   
}