BZOJ 2843 极地旅行社

题目大意

维护一棵树，每个点有1个权值，请你维护它，支持单点修改，动态连边，查询$u \to v$路径上的点权和。

LCT维护即可。

很好写，很快就A了。

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

#define N 30010

int n,m,ix,iy,v[N],t[N],fa[N],c[2][N];
char md;
bool rev[N];

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 bool isroot(int pos) {return c[0][fa[pos]]!=pos&&c[1][fa[pos]]!=pos;}

inline void pushdown(int pos)
{
	if(rev[pos])
	{
		rev[c[0][pos]]^=1,rev[c[1][pos]]^=1;
		swap(c[0][c[0][pos]],c[1][c[0][pos]]);
		swap(c[0][c[1][pos]],c[1][c[1][pos]]);
		rev[pos]=false;
	}
}

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

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;
	if(!isroot(ty)) c[(c[1][tz]==ty)][tz]=tx;
	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);//Forgot!!!
}

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

inline void access(int pos)
{
	int tmp=0;
	while(pos)
	{
		splay(pos);
		c[1][pos]=tmp;//,fa[tmp]=pos; NOT NEEDED
		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 int lookfor(int pos)
{
	access(pos),splay(pos);//Forgot to write "access(pos)"
	while(c[0][pos]) pos=c[0][pos];
	return pos;
}

inline bool link(int tx,int ty)
{
	if(lookfor(tx)!=lookfor(ty))
		{chroot(tx),fa[tx]=ty;return true;}
		//{splay(tx),fa[tx]=ty;return true;}
	return false;
}

inline void update(int tx,int ty)
{
	splay(tx);
	v[tx]=v[tx]-t[tx]+ty;
	t[tx]=ty;
}

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

int main()
{
	n=RI();
	for(int i=1;i<=n;++i) v[i]=t[i]=RI();
	m=RI();
	while(m--)
	{
		md=getchar();
		while(md!='b'&&md!='p'&&md!='e') md=getchar();
		switch(md)
		{
			case 'b':
			{
				ix=RI(),iy=RI();
				printf("%s\n",link(ix,iy)?"yes":"no");
				break;
			}
			case 'p':
			{
				ix=RI(),iy=RI();
				update(ix,iy);
				break;
			}
			case 'e':
			{
				ix=RI(),iy=RI();
				if(lookfor(ix)!=lookfor(iy)) printf("impossible\n");
				else printf("%d\n",query(ix,iy));
				break;
			}
		}
	}
}