和LightOJ1257一样，之前我用了树分治写了。其实原来这题是道经典的树形DP，感觉这个DP不简单。。
- dp[0][u]表示以u为根的子树中的结点与u的最远距离
- dp[1][u]表示以u为根的子树中的结点与u的次远距离
这两个可以一遍dfs通过儿子结点转移得到。显然dp[0][u]就是u的一个可能的答案，即u往下走的最远距离，还缺一部分就是u往上走的最远距离：
- dp[2][u]表示u往上走的最远距离
对于这个的转移，分两种情况，是这样的：
- dp[2][v] = max( dp[0][u]+weight(u,v) , dp[2][u]+weight(u,v) ) （v是u的儿子 且 u往下走的最远距离不经过v）
- dp[2][v] = max( dp[1][u]+weight(u,v) , dp[2][u]+weight(u,v) ) （v是u的儿子 且 u往下走的最远距离经过v）
再一遍dfs就能得到。每个u的答案就是max(dp[0][u],dp[2][u]);
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 11111
struct Edge{
int v,w,next;
}edge[MAXN<<];
int NE,head[MAXN];
void addEdge(int u,int v,int w){
edge[NE].v=v; edge[NE].w=w;
edge[NE].next=head[u]; head[u]=NE++;
}
long long d[][MAXN];
int idx[MAXN];
void dfs0(int u,int fa){
long long mx0=,mx1=;
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(v==fa) continue;
dfs0(v,u);
if(mx0<=d[][v]+edge[i].w) mx1=mx0,mx0=d[][v]+edge[i].w,idx[u]=v;
else if(mx1<d[][v]+edge[i].w) mx1=d[][v]+edge[i].w;
else if(mx1<d[][v]+edge[i].w) mx1=d[][v]+edge[i].w;
}
d[][u]=mx0; d[][u]=mx1;
}
void dfs1(int u,int fa){
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(v==fa) continue;
if(idx[u]==v) d[][v]=max(d[][u]+edge[i].w,d[][u]+edge[i].w);
else d[][v]=max(d[][u]+edge[i].w,d[][u]+edge[i].w);
dfs1(v,u);
}
}
int main(){
int n,a,b;
while(~scanf("%d",&n)){
NE=;
memset(head,-,sizeof(head));
for(int i=; i<=n; ++i){
scanf("%d%d",&a,&b);
addEdge(i,a,b); addEdge(a,i,b);
}
memset(d,,sizeof(d));
dfs0(,);
dfs1(,);
for(int i=; i<=n; ++i){
printf("%lld\n",max(d[][i],d[][i]));
}
}
return ;
}