记录编号	367580	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[WC 2014] 紫荆花之恋	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	102.511 s
提交时间	2017-01-31 18:35:59	内存使用	56.77 MiB

#include<cstdio>
#include<set>
using namespace std;
const int N=2e5+10;
struct edge{int f,t,l;}w[N];
int T,n,c[N],head[N],tail[N],next[N];
void add(int f,int t,int l){
	static int cnt=0;
	w[++cnt]=(edge){f,t,l};
	if (!head[f]) head[f]=tail[f]=cnt;
		else tail[f]=next[tail[f]]=cnt;
	w[++cnt]=(edge){t,f,l};
	if (!head[t]) head[t]=tail[t]=cnt;
		else tail[t]=next[tail[t]]=cnt;
}
struct BST{
	struct node{
		int s,k;
		node *lc,*rc;
		node(int K){k=K;s=1;lc=rc=0;}
		node(node *x){
			s=x->s;k=x->k;
			lc=x->lc?new node(x->lc):0;
			rc=x->rc?new node(x->rc):0;
		}
		~node(){delete lc;delete rc;}
	}*root;
	void operator = (const BST x){
		clear();
		if (x.root) root=new node(x.root);
	}
	void clear(){delete root;root=0;}
	int size(node *x){return !x?0:x->s;}
	void update(node *x){x->s=size(x->lc)+size(x->rc)+1;}
	void l_rot(node *&x){
		node *y=x->rc;
		x->rc=y->lc;y->lc=x;
		update(x);update(y);
		x=y;
	}
	void r_rot(node *&x){
		node *y=x->lc;
		x->lc=y->rc;y->rc=x;
		update(x);update(y);
		x=y;
	}
	void mt(node *&x,bool y){
		if (y){
			if (!x->rc) return;
			if (size(x->rc->rc)>size(x->lc)) l_rot(x);else
			if (size(x->rc->lc)>size(x->lc))
				r_rot(x->rc),l_rot(x);
			else return;
		}
		else{
			if (!x->lc) return;
			if (size(x->lc->lc)>size(x->rc)) r_rot(x);else
			if (size(x->lc->rc)>size(x->rc))
				l_rot(x->lc),r_rot(x);
			else return;
		}
		mt(x->lc,0);mt(x->rc,1);mt(x,1),mt(x,0);
	}
	void insert(int key){insert(root,key);}
	void insert(node *&x,int key){
		if (!x){x=new node(key);return;}
		x->s++;
		insert(key>x->k?x->rc:x->lc,key);
		mt(x,key>x->k);
	}
	int rank(int key){
		int ans=0;
		for (node *x=root;x;)
			if (key>=x->k) ans+=size(x->lc)+1,x=x->rc;
				else x=x->lc;
		return ans;
	}
}Tree[N],up[N];
//分治树重构与询问 
set<int> son[N];
long long ans;
int Q[N],size,fa[N],s[N],r[N],h[N],Size[N],dep[N],dis[N][50];
void Set(int x,int Fa){
	if (fa[x]) son[fa[x]].erase(x);
	fa[x]=Fa;
	if (Fa) son[Fa].insert(x);
}
void get_sub(int x){
	Q[++size]=x;
	for (set<int>::iterator i=son[x].begin();i!=son[x].end();++i) get_sub(*i);
}
int Tree_size,Root,big[N],vis[N];
void getroot(int x,int Fa,int C){
	s[x]=1;big[x]=0;
	for (int i=head[x];i;i=next[i]){
		int v=w[i].t;
		if (v==Fa||vis[v]!=C) continue;
		getroot(v,x,C);
		s[x]+=s[v];
		if (s[v]>big[x]) big[x]=s[v];
	}
	if (s[x]>=Tree_size/2&&big[x]<=Tree_size/2) Root=x;
}
void geth(int x,int Fa,int C,BST &T,bool tp){
	if (tp) dis[x][++h[x]]=dep[x];
	T.insert(dep[x]-r[x]);s[x]=1;
	for (int i=head[x];i;i=next[i]){
		int v=w[i].t;
		if (vis[v]!=C||v==Fa) continue;
		dep[v]=dep[x]+w[i].l;
		geth(v,x,C,T,tp);
		s[x]+=s[v];
	}
}
void build(int x,int C){
	Tree[x].clear();
	dep[x]=0;
	geth(x,0,C,Tree[x],1);
	vis[x]=0;
	Size[x]=s[x];
	for (int i=head[x];i;i=next[i]){
		int v=w[i].t;
		if (vis[v]!=C) continue;
		Tree_size=s[v];
		getroot(v,0,C);
		Set(Root,x);
		up[Root].clear();
		geth(v,0,C,up[Root],0);
		build(Root,C);
	}
}
int query(int p,int D){//树上到p距离与r之差不超过D的点个数 
	int ans=0;
	for (int x=p;x;x=fa[x]){
		ans+=Tree[x].rank(D-dis[p][h[x]]);
		if (fa[x]) ans-=up[x].rank(D-dis[p][h[x]-1]);
	}
	return ans;
}
int main()
{
	freopen("flowera.in","r",stdin);
	freopen("flowera.out","w",stdout);
	scanf("%d%d",&T,&n);
	scanf("%d%d%d",&fa[1],&c[1],&r[1]);
	Size[1]=h[1]=1;Tree[1].insert(-r[1]);
	puts("0");
	for (int i=2;i<=n;i++){
		scanf("%d%d%d",&fa[i],&c[i],&r[i]);
		fa[i]^=ans%1000000000;
		add(fa[i],i,c[i]);
		ans+=query(fa[i],r[i]-c[i]);
		printf("%lld\n",ans);
		int u=fa[i];Set(i,u);
		Size[i]=1;h[i]=h[u]+1;
		for (int x=u;x;x=fa[x])
			Size[x]++,dis[i][h[x]]=dis[u][h[x]]+c[i];
		for (int x=i;x;x=fa[x]){
			Tree[x].insert(dis[i][h[x]]-r[i]);
			if (fa[x]) up[x].insert(dis[i][h[x]-1]-r[i]);
		}
		int v=0;
		for (int x=i;fa[x];x=fa[x])
			if (Size[x]>Size[fa[x]]*0.7+5) v=fa[x];
		if (v){
			size=0;get_sub(v);
			static int C=0;C++;
			int Fa=fa[v];
			for (int i=1;i<=size;i++)
				vis[Q[i]]=C,h[Q[i]]=h[Fa];
			Tree_size=size;
			getroot(v,0,C);
			up[Root]=up[v];
			Set(Root,Fa);
			build(Root,C);
		}
	}
	return 0;
}