记录编号	336859	评测结果	AAAAAAAAAA
题目名称	最长链	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	0.060 s
提交时间	2016-11-03 18:51:30	内存使用	0.79 MiB

#include<cstdio>
#include<algorithm>
#define file(x) "length."#x
using std::max;
const int V=10010,E=V<<1;
struct EDGE{int u,v,w;}st[E];
int n,hed[V],nxt[E],f[V][2],ans[V],f2[V];
void _add(int u,int v,int w){
	static int sz=0;
	st[++sz].u=u,st[sz].v=v,st[sz].w=w;
	nxt[sz]=hed[u],hed[u]=sz;
}
void add(int u,int v,int w){
	_add(u,v,w),_add(v,u,w);
}
//f[u]到子树中的最大距离和次大 
void dfs1(int u,int fa){
	int v;
	for(int e=hed[u];e;e=nxt[e]) if((v=st[e].v)!=fa){
		dfs1(v,u);
		if(f[v][0]+st[e].w>f[u][0]) f[u][1]=f[u][0],f[u][0]=f[v][0]+st[e].w;
		else if(f[v][0]+st[e].w>f[u][1]) f[u][1]=f[v][0]+st[e].w;
	}
}
//f2[u]非子树的最大距离 
void dfs2(int u,int fa){
	int v;
	for(int e=hed[u];e;e=nxt[e]) if((v=st[e].v)!=fa){
		int t;
		if(f[v][0]+st[e].w==f[u][0]) t=f[u][1]+st[e].w;
		else t=f[u][0]+st[e].w;
		f2[v]=max(f2[u]+st[e].w,t);
		dfs2(v,u);
	}
}
int main(){
	freopen(file(in),"r",stdin);
	freopen(file(out),"w",stdout);
	scanf("%d",&n);
	for(int i=2;i<=n;i++) {
		int v,w;scanf("%d%d",&v,&w);
		add(i,v,w);
	}
	dfs1(1,0);
	dfs2(1,0);
	for(int i=1;i<=n;i++) printf("%d\n",max(f[i][0],f2[i]));
}