记录编号	305576	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[WC 2014] 紫荆花之恋	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	183.934 s
提交时间	2016-09-10 21:31:29	内存使用	346.24 MiB

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;
const int N=100010,M=20000010;
int cnt,fir[N],to[N*2],val[N*2],nxt[N*2];
void addedge(int a,int b,int v){
	nxt[++cnt]=fir[a];
	to[fir[a]=cnt]=b;
	val[cnt]=v;
}
int pim,top,pool[N],sz[M];
int ch[M][2],key[M],fix[M];
#define lc ch[x][0]
#define rc ch[x][1]
int Newnode(int k){
	int x=top?pool[top--]:++pim;
	sz[x]=1;lc=rc=0;key[x]=k;
	fix[x]=rand();return x;
}
#define c (k>=key[x])
#define g ch[x][c] 

void Push_up(int x){sz[x]=sz[lc]+sz[rc]+1;}

void Rotate(int x,int &y,int f){
	ch[y][f]=ch[x][f^1];ch[x][f^1]=y;
	Push_up(y);Push_up(x);y=x;
}

void Insert(int &x,int k){
	if(!x){x=Newnode(k);return;}Insert(g,k);
	sz[x]+=1;if(fix[x]>fix[g])Rotate(g,x,c);
}

int Query(int x,int k){
	if(!x)return 0;
	if(!c)return Query(g,k);
	return Query(g,k)+sz[lc]+1;
}

void Delete(int &x){
	if(!x)return;
	pool[++top]=x;x=0;
	if(lc)Delete(lc);
	if(rc)Delete(rc);
}

long long ans;
int n,fa[N],v[N],r[N];
int rt[N],pt[N],dep[N];
int G[N][50],SZ[N],P,w,tp;
int F[N],H[N],S,mm;

void Get_G(int x,int f,int d){
	F[x]=H[x]=1;
	for(int i=fir[x];i;i=nxt[i])
		if(to[i]!=f&&dep[to[i]]>=d){
			Get_G(to[i],x,d);
			H[x]=max(H[x],F[to[i]]);
			F[x]+=F[to[i]];
		}
	H[x]=max(H[x],S-F[x]);
	if(!P||H[P]>H[x])P=x;
}

void DFS(int x,int f,int d,int v,int &t){
	F[x]=1;dep[x]=d+1;
	G[x][d]=v;Insert(t,v-r[x]);
	for(int i=fir[x];i;i=nxt[i])
		if(to[i]!=f&&dep[to[i]]>=d){
			DFS(to[i],x,d,v+val[i],t);
			F[x]=F[x]+F[to[i]];
		}
}

void Rebuild(int x,int f,int d,int m,int sz){
	P=0;S=sz;Get_G(x,0,d);fa[x=P]=f;Delete(rt[x]);
	SZ[x]=sz;DFS(x,0,d,0,rt[x]);dep[x]=d;
	if(pt[x]!=mm)Delete(pt[x]);pt[x]=m;
	for(int i=fir[x],p;i;i=nxt[i])
		if(dep[to[i]]>=d){
			p=0;DFS(to[i],0,d+1,val[i],p);
			Rebuild(to[i],x,d+1,p,F[to[i]]);
		}
}

int main(){
	freopen("flowera.in","r",stdin);
	freopen("flowera.out","w",stdout);
	scanf("%d%d",&tp,&n);
	scanf("%d%d%d",fa+1,v+1,r+1);
	Insert(rt[1],-r[1]);SZ[1]=1;puts("0");	
	for(int x=2;x<=n;x++){
		scanf("%d%d%d",fa+x,v+x,r+x);
		fa[x]^=ans%1000000000;
		addedge(x,fa[x],v[x]);
		addedge(fa[x],x,v[x]);
		dep[x]=dep[fa[x]]+1;
		
		for(int i=0;i<dep[x];i++)
			G[x][i]=G[fa[x]][i]+v[x];
		
		for(int y=x;y!=0;y=fa[y]){
			SZ[y]+=1;w=r[x]-G[x][dep[y]];
			ans+=Query(rt[y],w);
			Insert(rt[y],-w);
			if(fa[y]){
				w=r[x]-G[x][dep[fa[y]]];
				ans-=Query(pt[y],w);
				Insert(pt[y],-w);
				if(SZ[y]>SZ[fa[y]]*.88)P=fa[y];
			}
		}
		printf("%lld\n",ans);
		if(P)Rebuild(P,fa[P],dep[P],mm=pt[P],SZ[P]),P=0;
	}
	return 0;
}