记录编号	134142	评测结果	AAAAAAAAAA
题目名称	最长链	最终得分	100
用户昵称	奶猹	是否通过	通过
代码语言	C++	运行时间	0.026 s
提交时间	2014-10-29 15:45:40	内存使用	0.55 MiB

#include<cstdio>
const short sizeque=1500;

int n;
struct aaa{
	short to;
	short next;
	int data;
}a[20001];
short head0[10001];
short tot=0;
int dis0[10001],dis1[10001];
bool b[10001];
short rec0,rec1;
int ans;
int q[sizeque],head=1,tail=0;//循环队列头、尾指针

inline void init();
inline void spfa();
inline void outit();
inline void insert(int ,int ,int );
inline int front(){return q[(head)%sizeque];} //队列的各种操作
inline void push(int x){q[(++tail)%sizeque]=x;}
inline void pop(){head++;}
inline bool empty(){return head>tail;}
inline int max(int a,int b){if(a>b)return a;else return b;}

int main()
{
	freopen("length.in","r",stdin);
	freopen("length.out","w",stdout);
	init();
	spfa();
	outit();
	fclose(stdin);
	fclose(stdout);
	return 0;
}
inline void init()
{
	scanf("%d",&n);
	int x,v;
	for(int i=2;i<=n;i++)
	{
		scanf("%d%d",&x,&v);
		insert(x,i,v);
		insert(i,x,v);
	}
}
inline void spfa()
{
	for(int i=1;i<=n;i++)
	dis0[i]=dis1[1]=b[i]=0;
	push(1);
	b[1]=1;
	rec0=1;
	while(!empty())
	{
		int k=front();
		for(int i=head0[k];i;i=a[i].next)
		{
			int t=a[i].to;
			if(!b[t])
			{
				push(t);
			 	b[t]=1;
			 	dis0[t]=dis0[k]+a[i].data;
			}
		}
		pop();
	}
	for(int i=1;i<=n;i++)
	if(dis0[i]>dis0[rec0]) rec0=i;//找一个最远点
	for(int i=1;i<=n;i++)
	dis0[i]=b[i]=0;
	push(rec0);
	b[rec0]=1;
	dis0[rec0]=0;
	while(!empty())
	{
		int k=front();
		pop();
		for(int i=head0[k];i;i=a[i].next)
		{
			int t=a[i].to;
	 		{
				if(!b[t])
				{
					dis0[t]=dis0[k]+a[i].data;
					push(t);
					b[t]=1;
				}
			}
		}		
	}
	rec1=1;
	for(int i=1;i<=n;i++)//找另一个最远点，因为最后一个出队的不一定最远
	if(dis0[i]>dis0[rec1]) rec1=i;
	for(int i=1;i<=n;i++)
	b[i]=0;
	push(rec1);
	b[rec1]=1;
	dis1[rec1]=0;
	while(!empty())
	{
		int k=front();
		for(int i=head0[k];i;i=a[i].next)
		{
			int t=a[i].to;
			if(!b[t])
			{
				dis1[t]=dis1[k]+a[i].data;
				push(t);
				b[t]=1;
			}
				
		}
		pop();
		b[k]=1;
	}
	
}
inline void outit()
{
	for(int i=1;i<=n;i++)
	printf("%d\n",max(dis0[i],dis1[i]));
}
inline void insert(int x,int y,int v)
{
	tot++;
	a[tot].to=y;
	a[tot].next=head0[x];
	a[tot].data=v;
	head0[x]=tot;
}