记录编号	293133	评测结果	AAAAAAAAAA
题目名称	最长链	最终得分	100
用户昵称	Hzoi_chairman	是否通过	通过
代码语言	C++	运行时间	0.023 s
提交时间	2016-08-09 19:03:21	内存使用	1.11 MiB

#include<iostream>
#include<cstdio>
#define maxe 30000
#define maxn 20000 
using namespace std;
int read()
{
	int x,f=1;
	char ch;
	while(ch=getchar(),!isdigit(ch))if(ch=='-')f=-1;
	x=ch-48;
	while(ch=getchar(),isdigit(ch))x=x*10+ch-48;
	return x*f;
}
struct edge
{
	int t,n;int d;
}a[maxe];
int len,head[maxn],fa[maxn],dis[maxn],son[maxn],maxa[maxn],maxb[maxn];
void insert(int x,int y,int z)
{
	a[++len].t=y;a[len].d=z;a[len].n=head[x];head[x]=len;
}
#define k a[i].t
void dfs(int x)
{
	for(int i=head[x];i;i=a[i].n)
	{
		if(fa[x]==k)continue;
		fa[k]=x;dis[k]=a[i].d;
		dfs(k);
		if(a[i].d+maxa[k]>maxa[x])
		{
			maxb[x]=maxa[x];maxa[x]=maxa[k]+a[i].d;son[x]=k;//注意最长和次长不能有重合路径，次长并不是严格的次长 
		}
		else if(a[i].d+maxa[k]>maxb[x])maxb[x]=a[i].d+maxa[k];
	}
}
#undef k
int ans;
void work(int x)
{
	int an=0,now=maxa[x];
	while(fa[x])
	{
		an+=dis[x];
		now+=dis[x];
		int aa=an;
		if(son[fa[x]]==x)aa+=maxb[fa[x]];//记录son比较方便，如果判断距离有可能错 
		else aa+=maxa[fa[x]];
		ans=max(ans,aa);
		x=fa[x];
	}
}
int main()
{
	freopen("length.in","r",stdin);
	freopen("length.out","w",stdout);
	int n=read();
	for(int i=2;i<=n;i++)
	{
		int x=read(),y=read();
		insert(i,x,y);
		insert(x,i,y);
	}
	dfs(1);
	printf("%d\n",maxa[1]);
	for(int i=2;i<=n;i++)
	{
		ans=maxa[i];
		work(i);
		printf("%d\n",ans);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
/*
其实也挺暴力
每个点的最长路径是其与远房或晚辈的距离
*/