记录编号	293067	评测结果	AAAAAAAAAA
题目名称	最长链	最终得分	100
用户昵称	安呐一条小咸鱼。	是否通过	通过
代码语言	C++	运行时间	0.025 s
提交时间	2016-08-09 17:48:45	内存使用	1.01 MiB

#include <cstdio>
#include <iostream>
#define maxn 10100
using namespace std;
typedef long long LL;
int a,b,n;
struct Edge{
	LL next,to,dis;
}edge[maxn<<1];
int head[maxn],tot;
void Addedge(int x,int y,int z){
	edge[++tot].to=y;
	edge[tot].dis=z;
	edge[tot].next=head[x];
	head[x]=tot;
}
int d1[maxn],d2[maxn],dn[maxn],maxans[maxn],depth[maxn];
int dfs1(int x)
{
	d1[x]=depth[x];
	for(int i=head[x];i;i=edge[i].next)
	{
		int to=edge[i].to;
		depth[to]=depth[x]+edge[i].dis;
		int d=dfs1(to);
		if(d1[x]<=d){
			d2[x]=d1[x];
			d1[x]=d;
			dn[x]=to;
		}
		else
		{
			d2[x]=max(d2[x],d);
		}
	}
	return d1[x];
}
void dfs2(int x,int y)
{
	maxans[x]=max(y,d1[x]-depth[x]);
	for(int i=head[x];i;i=edge[i].next)
	{
		int to=edge[i].to;
		if(to==dn[x])
		{
			dfs2(to,max(y,d2[x]-depth[x])+edge[i].dis);
		}
		else
		{
			dfs2(to,max(y,d1[x]-depth[x])+edge[i].dis);
		}
	}
}
int main(){
	freopen("length.in", "r", stdin); freopen("length.out", "w", stdout);
	scanf("%d",&n);
	for(int i=2;i<=n;i++)
	{
		scanf("%d%d",&a,&b);
		Addedge(a,i,b);
	}
	dfs1(1);
	dfs2(1,0);
	for(int i=1;i<=n;i++){
		printf("%d\n",maxans[i]);
	}
	getchar();getchar();getchar();
	return 0;
}