记录编号	293171	评测结果	WWWWWWWWWW
题目名称	最长链	最终得分	0
用户昵称	AntiLeaf	是否通过	未通过
代码语言	C++	运行时间	0.040 s
提交时间	2016-08-09 19:23:26	内存使用	0.98 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10010;
struct edge{
	int to,dis,prev;
	edge():prev(0){}
}e[maxn<<1];
void insert(int,int,int);
void dfs1(int);
void dfs2(int,int);
void query(int);
int n,prt[maxn],top[maxn],son[maxn],disa[maxn],disb[maxn],disc[maxn],disp[maxn];
//abc分别表示到链底的距离、轻子树距离最大值、到链顶的距离、到父亲的距离
int sone[maxn],bottom[maxn],xb[maxn],x,z;
int len=0,last[maxn]={0},root,ans[maxn]={0};
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",&x,&z);
		insert(x,i,z);
		insert(i,x,z);
	}
	dfs1(1);
	dfs2(1,1);
	for(int i=1;i<=n;i++)query(i);
	for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
	//for(int i=1;i<=n;i++)printf("i=%d top=%d prt=%d son=%d disa=%d disb=%d disc=%d disp=%d\n",i,top[i],prt[i],son[i],disa[i],disb[i],disc[i],disp[i]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}
void insert(int x,int y,int z){
	e[++len].to=y;
	e[len].dis=z;
	e[len].prev=last[x];
	last[x]=len;
}
void dfs1(int x){//求出重儿子、disa和disb
#define y e[i].to
	for(int i=last[x];i;i=e[i].prev){
		if(y==prt[x])continue;
		prt[y]=x;
		disp[y]=e[i].dis;
		dfs1(y);
		if(disa[y]+e[i].dis>disa[x]){//更新disa和重儿子
			sone[x]=i;
			xb[x]=son[x];
			son[x]=y;
			disb[x]=disa[x];//更新disb(非重儿子中的最长距离)
			disa[x]=disa[y]+e[i].dis;
		}
		else if(disa[y]+e[i].dis>disb[x]){
			disb[x]=disa[y]+e[i].dis;
			xb[x]=y;
		}
	}
}
void dfs2(int x,int tp){//求出top和disc
	top[x]=tp;
	if(son[x]){
		disc[son[x]]=disc[x]+e[sone[x]].dis;
		dfs2(son[x],tp);
	}
	for(int i=last[x];i;i=e[i].prev){
		if(y==prt[x]||y==son[x])continue;
		dfs2(y,y);
	}
#undef y
}
void query(int x){
	int rt=x,dis=0,y;
	bool frson=false;
	while(rt){
		if(frson){
			if(ans[x]<disb[rt]+dis){
				y=bottom[xb[rt]];
				ans[x]=disb[rt]+dis;
			}
		}
		else{
			if(ans[x]<disa[rt]+dis){
				y=bottom[rt];
				ans[x]=disa[rt]+dis;
			}
		}
		if(top[rt]!=rt){
			dis+=disc[rt];
			rt=top[rt];
			frson=true;
		}
		else{
			dis+=disp[rt];
			rt=prt[rt];
			frson=false;
		}
	}
	if(ans[y]>ans[x])ans[x]=ans[y];
	else if(ans[x]>ans[y])ans[y]=ans[x];
}
/*
3
1 1
1 2
Answer:
2
3
3
*/
/*
11
1 1
2 2
2 6
6 3
1 9
5 1
6 2
10 2
6 4
5 7
Answer:
19
20
22
26
19
16
20
18
22
20
26
*/
/*
解法：
使用树链剖分，但这次不再使用重链剖分法，而是使用另一种剖分方法：
将所有儿子中最大距离所在子树的根作为重儿子，记录到链底的距离和次大距离。
这样每个点距离最大就有两种情况：
1.从它到链底
2.从它往上跳，只处理途中链顶的次大距离+它到目前节点的距离。
要实现第二种情况，必须记录一个东西表示它到链顶的距离。
复杂度应该介于重链剖分法和深度剖分法之间或略大于深度剖分法，
即O(sqrt(n))。
还是比较够用的。
顺便一提这是在线算法，虽然并不需要在线。
(好吧其实这是伪树剖...连dfs序都没有算什么树剖)
*/