题目
博主讲的很好:https://blog.csdn.net/u013480600/article/details/21831363
#include
#define en '\n'
#define m(a,b) memset(a,b,sizeof a)
using namespace std;
typedef long long ll;
const int N=1e4+5;
struct Edge{int to;ll len;int nex;}edge[N<<1];
int head[N],tot;
inline void add(int from,int to,ll len){edge[&#43;&#43;tot]&#61;(Edge){to,len,head[from]};head[from]&#61;tot;edge[&#43;&#43;tot]&#61;(Edge){from,len,head[to]};head[to]&#61;tot;
}
ll dp[N][3];int son[N];
void dfs1(int x,int fa){dp[x][0]&#61;dp[x][1]&#61;dp[x][2]&#61;0;for(int i&#61;head[x];i;i&#61;edge[i].nex){int y&#61;edge[i].to;ll w&#61;edge[i].len;if(y&#61;&#61;fa) continue;dfs1(y,x);if(dp[x][0]<dp[y][0]&#43;w){dp[x][1]&#61;max(dp[x][1],dp[x][0]);dp[x][0]&#61;dp[y][0]&#43;w,son[x]&#61;y;}else dp[x][1]&#61;max(dp[x][1],dp[y][0]&#43;w);}
}
void dfs2(int x,int fa){for(int i&#61;head[x];i;i&#61;edge[i].nex){int y&#61;edge[i].to;ll w&#61;edge[i].len;if(y&#61;&#61;fa) continue;if(son[x]&#61;&#61;y) dp[y][2]&#61;max(dp[x][1],dp[x][2])&#43;w;else dp[y][2]&#61;max(dp[x][0],dp[x][2])&#43;w;dfs2(y,x);}
}
int main(){int n;while(~scanf("%d",&n)){m(head,0),tot&#61;0;for(int i&#61;2;i<&#61;n;&#43;&#43;i){int y;ll w;scanf("%d%lld",&y,&w);add(i,y,w);}dfs1(1,1),dfs2(1,1);for(int i&#61;1;i<&#61;n;&#43;&#43;i) printf("%d\n",max(dp[i][0],dp[i][2]));}
}