BZOJ 2631 tree

2017.11.20

题目大意

维护一颗树，支持：

  1. $u \to v$的路径上的点的权值加上自然数c
  2. 删除边$u_1 \to v_1$,加入边$u_2 \to v_2$
  3. $u \to v$的路径上的点的权值乘上自然数c
  4. 询问路径$u \to v$上的点的权值和

这题LCT维护下。

重点是这题卡longlong......需要压成unsigned int才能过......

#include <cstdio>
#include <algorithm>
using namespace std;

#define N 100010
#define MO 51061

int n,q,ia,ib,ic,siz[N],c[2][N],fa[N];
unsigned int v[N],t[N],lzu[N],lzm[N];
bool rev[N];
int to[N<<1],nex[N<<1],head[N],tot;

inline int RI()
{
	int ret=0;
	char tmp=getchar();
	while(tmp<'0'||tmp>'9') tmp=getchar();
	while(tmp>='0'&&tmp<='9') ret=ret*10+tmp-'0',tmp=getchar();
	return ret;
}

inline void AE(int tx,int ty) {to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot;}

void DFS(int pos,int pre)
{
	for(int i=head[pos];i;i=nex[i])
		if(to[i]!=pre)
			fa[to[i]]=pos,DFS(to[i],pos);
}

inline bool isroot(int pos) {return c[0][fa[pos]]!=pos&&c[1][fa[pos]]!=pos;}

inline void pushup(int pos)
{
	siz[pos]=siz[c[0][pos]]+siz[c[1][pos]]+1;
	v[pos]=(v[c[0][pos]]+v[c[1][pos]]+t[pos])%MO;
}

inline void pushdown(int pos)
{
	if(lzm[pos]!=1)
	{
		v[c[0][pos]]=(v[c[0][pos]]*lzm[pos])%MO,v[c[1][pos]]=(v[c[1][pos]]*lzm[pos])%MO;
		t[c[0][pos]]=(t[c[0][pos]]*lzm[pos])%MO,t[c[1][pos]]=(t[c[1][pos]]*lzm[pos])%MO;
		lzm[c[0][pos]]=(lzm[c[0][pos]]*lzm[pos])%MO,lzm[c[1][pos]]=(lzm[c[1][pos]]*lzm[pos])%MO;
		lzu[c[0][pos]]=(lzu[c[0][pos]]*lzm[pos])%MO,lzu[c[1][pos]]=(lzu[c[1][pos]]*lzm[pos])%MO;
		lzm[pos]=1;
	}
	if(lzu[pos])
	{
		v[c[0][pos]]=(v[c[0][pos]]+lzu[pos]*siz[c[0][pos]])%MO,v[c[1][pos]]=(v[c[1][pos]]+lzu[pos]*siz[c[1][pos]])%MO;
		t[c[0][pos]]=(t[c[0][pos]]+lzu[pos])%MO,t[c[1][pos]]=(t[c[1][pos]]+lzu[pos])%MO;
		lzu[c[0][pos]]=(lzu[c[0][pos]]+lzu[pos])%MO,lzu[c[1][pos]]=(lzu[c[1][pos]]+lzu[pos])%MO;
		lzu[pos]=0;
	}
	if(rev[pos])
	{
		swap(c[0][c[0][pos]],c[1][c[0][pos]]);
		swap(c[0][c[1][pos]],c[1][c[1][pos]]);
		rev[c[0][pos]]^=1,rev[c[1][pos]]^=1;
		rev[pos]=false;
	}
}

void init(int pos)
{
	if(!isroot(pos)) init(fa[pos]);
	pushdown(pos);
}

inline void rotate(int tx)
{
	int ty=fa[tx],tz=fa[ty],tl=(c[1][ty]==tx),tr=tl^1;//c[1][ty]==tx
	if(!isroot(ty)) c[c[1][tz]==ty][tz]=tx;//c[1][tz]==ty
	fa[tx]=tz,fa[ty]=tx;
	fa[c[tr][tx]]=ty,c[tl][ty]=c[tr][tx],c[tr][tx]=ty;
	pushup(ty),pushup(tx);
}

inline void splay(int tx)
{
	init(tx);//init(tx);
	while(!isroot(tx))
	{
		int ty=fa[tx],tz=fa[ty];
		if(!isroot(ty))
		{
			if((c[0][ty]==tx)^(c[0][tz]==ty)) rotate(tx);
			else rotate(ty);
		}
		rotate(tx);
	}
}

inline void access(int pos)
{
	//init(pos); NOT NEEDED
	int tmp=0;
	while(pos)
	{
		splay(pos);
		c[1][pos]=tmp;
		pushup(pos);
		tmp=pos,pos=fa[pos];
	}
}

inline void chroot(int pos)
{
	access(pos),splay(pos);
	swap(c[0][pos],c[1][pos]);
	rev[pos]^=1;
}

inline void link(int tx,int ty)
{
	chroot(tx),fa[tx]=ty;
}

inline void cut(int tx,int ty)
{
	//chroot(tx),splay(ty); WRONG!
	chroot(tx),access(ty),splay(ty);
	c[0][ty]=fa[tx]=0;
	pushup(ty);
}

inline void add(int tx,int ty,unsigned int tz)
{
	chroot(tx),access(ty),splay(ty);
	t[ty]=(t[ty]+tz)%MO,v[ty]=(v[ty]+1ll*tz*siz[ty])%MO,lzu[ty]=(lzu[ty]+tz)%MO;
}

inline void mul(int tx,int ty,int tz)
{
	chroot(tx),access(ty),splay(ty);
	t[ty]=(t[ty]*tz)%MO,v[ty]=(v[ty]*tz)%MO,lzu[ty]=(lzu[ty]*tz)%MO,lzm[ty]=(lzm[ty]*tz)%MO;
}

inline long long query(int tx,int ty)
{
	chroot(tx),access(ty),splay(ty);
	return v[ty]%MO;
}

int main()
{
	n=RI(),q=RI();
	for(int i=2;i<=n;++i) ia=RI(),ib=RI(),AE(ia,ib),AE(ib,ia);
	for(int i=1;i<=n;++i) v[i]=t[i]=1;
	DFS(1,0);
	while(q--)
	{
		char md=getchar();
		while(md!='+'&&md!='-'&&md!='*'&&md!='/') md=getchar();
		switch(md)
		{
			case '+': ia=RI(),ib=RI(),ic=RI(),add(ia,ib,ic);break;
			case '-': ia=RI(),ib=RI(),cut(ia,ib),ia=RI(),ib=RI(),link(ia,ib);break;
			case '*': ia=RI(),ib=RI(),ic=RI(),mul(ia,ib,ic);break;
			case '/': ia=RI(),ib=RI(),printf("%u\n",query(ia,ib));break;
		}
	}
}