记录编号	478099	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	2169.[WC 2014] 紫荆花之恋	最终得分	100
用户昵称	LadyLex	是否通过	通过
代码语言	C++	运行时间	71.100 s
提交时间	2017-12-08 17:15:10	内存使用	502.12 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
using namespace std;
#define LL long long
#define inf 1000000000
#define N 100010
#define alpha 0.755


int n,e,adj[N],val[N];
struct edge{int zhong,next;}s[N<<1];
inline void add(int qi,int zhong)
	{s[++e].zhong=zhong;s[e].next=adj[qi];adj[qi]=e;}
vector<int> to[N];
int f[N][18],bin[25],tp,deep[N],len[N];
inline int LCA(int a,int b)
{
	if(deep[a]<deep[b])a^=b,b^=a,a^=b;
	int i,cha=deep[a]-deep[b];
	for(i=tp;~i;--i)if(cha&bin[i])a=f[a][i];
	if(a==b)return a;
	for(i=tp;~i;--i)if(f[a][i]!=f[b][i])a=f[a][i],b=f[b][i];
	return f[a][0];
}
inline int dis(int a,int b){return len[a]+len[b]-len[LCA(a,b)]*2;}


struct Goat
{
	int val,size;Goat *ch[2];
	Goat(){}
	inline bool bad()
		{return ch[0]->size>=size*alpha+5 || ch[1]->size>=size*alpha+5; }
}*tree1[N],*tree2[N],mem[N<<8],*pool[N<<8],*null,*sta[N];
int tot,top;
inline void intn()
{
	null=new Goat();
	null->ch[0]=null->ch[1]=null,null->val=null->size=0;
	for(int i=0;i<(N<<8);++i)pool[i]=mem+i;
	tot=(N<<8)-1;
	for(int i=0;i<=n;++i)tree1[i]=tree2[i]=null;
}
inline Goat** insert(Goat *&a,int val)
{
	if(a==null)
	{
		a=pool[tot--],a->ch[0]=a->ch[1]=null;
		a->val=val,a->size=1;return &null;
	}
	++a->size;
	Goat **o=insert(a->ch[a->val<val],val);
	if(a->bad())o=&a;return o;
}
inline int get_rank(Goat *o,int val)
{
	if(o==null)return 0;
	return (o->val>=val)?get_rank(o->ch[0],val):(get_rank(o->ch[1],val)+o->ch[0]->size+1);
}
inline void Erholung(Goat *o)
{
	if(o==null)return;
	if(o->ch[0]!=null)Erholung(o->ch[0]);
	pool[++tot]=o;
	if(o->ch[1]!=null)Erholung(o->ch[1]);
}
inline void travel(Goat *o)
{
	if(o==null)return;
	if(o->ch[0]!=null)travel(o->ch[0]);
	sta[++top]=o;
	if(o->ch[1]!=null)travel(o->ch[1]);
}
inline Goat* build(int l,int r)
{
	if(l>r)return null;
	int mi=l+r>>1;
	Goat *o=sta[mi];o->size=r-l+1;
	o->ch[0]=build(l,mi-1),o->ch[1]=build(mi+1,r);
	return o;
}
inline void rebuild(Goat *&o){top=0,travel(o),o=build(1,top);}
inline void Insert(Goat *&a,int val)
{
	Goat **o=insert(a,val);
	if(*o!=null)rebuild(*o);
}


int size[N],maxs[N],totsize,root,Vater[N];
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
bool vis[N];
inline void dfs1(int rt,int fa)
{
	size[rt]=1,maxs[rt]=0;
	for(int i=adj[rt];i;i=s[i].next)
		if(!vis[s[i].zhong]&&s[i].zhong!=fa)
			dfs1(s[i].zhong,rt),size[rt]+=size[s[i].zhong],
			maxs[rt]=max(maxs[rt],size[s[i].zhong]);
	maxs[rt]=max(maxs[rt],totsize-size[rt]);
	if(maxs[rt]<maxs[root])root=rt;
}
inline void dfs2(int rt,int fa,int Vatti)
{
	// printf("ins:%d<-%d\n",rt,Vatti);
	Insert(tree1[Vatti],dis(rt,Vatti)-val[rt]);
	if(Vater[Vatti])Insert(tree2[Vatti],dis(rt,Vater[Vatti])-val[rt]);
	for(int i=adj[rt];i;i=s[i].next)
		if(s[i].zhong!=fa&&!vis[s[i].zhong])
			dfs2(s[i].zhong,rt,Vatti);
}
inline void dfs3(int rt,int fa)
{
	Vater[rt]=fa,vis[rt]=1;

	int siz=totsize;
	// printf("%d %d\n",rt,tree1[rt]->size);
	dfs2(rt,0,rt);
	// printf("%d %d\n",rt,tree1[rt]->size);

	for(int i=adj[rt];i;i=s[i].next)
		if(!vis[s[i].zhong])
		{
			if(size[s[i].zhong]>size[rt])totsize=siz-size[rt];
			else totsize=size[s[i].zhong];
			root=0,dfs1(s[i].zhong,rt),
			to[rt].push_back(root),dfs3(root,rt);
		}
}
inline void recover(int x)
{
	++totsize,vis[x]=0,
	Erholung(tree1[x]),Erholung(tree2[x]),
	tree1[x]=tree2[x]=null;
	for(int i=0,k=to[x].size();i<k;++i)
		recover(to[x][i]);
	to[x].clear();
}
inline void rebuild(int x)
{
	// printf("re:%d\n",x);
	totsize=0,recover(x),root=0,dfs1(x,0);
	if(Vater[x])
		for(int i=0,j=to[Vater[x]].size();i<j;++i)
			if(to[Vater[x]][i]==x)to[Vater[x]][i]=root;
	// printf("size=%d root=%d Vater=%d\n",totsize,root,Vater[x]);
	dfs3(root,Vater[x]);
}
LL ans=0;
inline int insert(int x)
{
	int rt,ds,ret=0;
	for(rt=x;Vater[rt];rt=Vater[rt])
		ds=val[x]-dis(x,Vater[rt])+1,ans+=get_rank(tree1[Vater[rt]],ds)-get_rank(tree2[rt],ds);
	for(rt=x;rt;rt=Vater[rt])
	{
		Insert(tree1[rt],dis(x,rt)-val[x]);
		if(Vater[rt])Insert(tree2[rt],dis(x,Vater[rt])-val[x]);
	}
	for(rt=x;Vater[rt];rt=Vater[rt])
		if(tree1[rt]->size>=tree1[Vater[rt]]->size*alpha+5)ret=Vater[rt];//*****
	return ret;
}

char B[1<<15],*S=B,*T=B;
#define getc (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
inline int read()
{
	int x=0;register char c=getc;
	while(c<'0'||c>'9')c=getc;
	while(c>='0'&&c<='9')x=10*x+(c^48),c=getc;
	return x;
}

int main()
{
	// freopen("Ark.in","r",stdin);
	freopen("flowera.in","r",stdin);
	freopen("flowera.out","w",stdout);
	n=read(),n=read();
	register int i,j,x,b;
	for(bin[0]=i=1;i<=20;++i)bin[i]=bin[i-1]<<1;
	while(bin[tp+1]<=n)++tp;
	maxs[0]=inf,root=0,intn();
	for(i=1;i<=n;++i)
	{

		Vater[i]=f[i][0]=read()^(ans%inf),b=read(),val[i]=read();
		// printf("%d %d\n",i,Vater[i]);
		deep[i]=deep[f[i][0]]+1,len[i]=len[f[i][0]]+b;vis[i]=1;
		if(Vater[i])to[Vater[i]].push_back(i),add(f[i][0],i),add(i,f[i][0]);
		for(int j=1;bin[j]+1<=deep[i];++j)f[i][j]=f[f[i][j-1]][j-1];
		x=insert(i);if(x)rebuild(x);
		printf("%lld\n",ans);
	}
}