HDU 2196 computer

#include <bits/stdc++.h>
using namespace std;

const int N(1e4+5);
//dp[0][u]:u到其后代的最长路
//dp[1][u]:u到其后代的次长路
int dp[3][N];
typedef pair<int,int> E;
vector<E> g[N];
//第一步向下走（一直向下走）
void dfs1(int u, int f){
    dp[0][u]=dp[1][u]=0;
    for(int i=0; i<g[u].size(); i++){
        int &v=g[u][i].first, &c=g[u][i].second;
        if(v==f) continue;
        dfs1(v, u);
        if(dp[0][u]<dp[0][v]+c){
            //注意更新dp[0][u]和dp[1][u]的顺序
            dp[1][u]=dp[0][u];
            dp[0][u]=dp[0][v]+c;
        }
        else dp[1][u]=max(dp[1][u], dp[0][v]+c);
    }
}
//第一步向上走
void dfs2(int u, int f){
    for(int i=0; i<g[u].size(); i++){
        int &v=g[u][i].first, &c=g[u][i].second;
        if(v==f) continue;
        //第二步向下走
        dp[2][v]=0;
        if(dp[0][u]==dp[0][v]+c){
            dp[2][v]=max(dp[2][v], dp[1][u]+c);
        }
        else{
            dp[2][v]=max(dp[2][v], dp[0][u]+c);
        }
        //第二步向上走(转移到u的第一步向上走)
        dp[2][v]=max(dp[2][v], dp[2][u]+c);
        dfs2(v, u);
    }
}
int main(){
    for(int n; ~scanf("%d", &n);){
        for(int i=1; i<=n; ++i) g[i].clear();
        for(int u=2, v, c; u<=n; ++u){
            scanf("%d%d", &v, &c); 
            g[u].push_back({v, c});
            g[v].push_back({u, c});
        }
        dfs1(1, 1);
        dp[2][1]=0;
        dfs2(1, 1);
        for(int i=1; i<=n; i++)
            printf("%d\n", max(dp[0][i], dp[2][i]));
    }
}