bzoj 3159 决战

树链剖分 + 非旋 treap.

考虑树剖,维护每条重链信息时,由于线段树无法支持翻转操作,把它换成非旋 treap .

给每个重链开一棵非旋 treap ,以深度作为下标.

前面四种操作可以直接做,对于翻转操作,可以把操作到的所有点合成一个 treap ,打完标记后再放回去.

修改操作保证了起点和终点有祖先后代关系,处理起来就简单一些了.

//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=5e4+10,inf=1e9;
char op[10];
int n,m,Root;
int ecnt=0,head[MAXN],to[MAXN<<1],nx[MAXN<<1];
void addedge(int u,int v)
{
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	head[u]=ecnt;
}
int idx=0,rt[MAXN];
struct node
{
	int ls,rs,fa,rev,tag,mx,mi,siz,info,weight;
	ll sum;
	node()
	{
		ls=rs=fa=rev=tag=info=0;
		mx=-inf,mi=inf;
		siz=0;
	}
}treap[MAXN];
#define root treap[o]
#define lson treap[root.ls]
#define rson treap[root.rs]
int newnode(int val)
{
	int o=++idx;
	root.weight=rand(),root.siz=1;
	root.info=root.sum=root.mx=root.mi=val;
	return idx;
}
void pushup(int o)
{
	root.sum=lson.sum+root.info+rson.sum;
	root.siz=lson.siz+1+rson.siz;
	root.mx=max(root.info,max(lson.mx,rson.mx));
	root.mi=min(root.info,min(lson.mi,rson.mi));
}
void reverse(int o)
{
	if(!o)
		return;
	root.rev^=1;
	swap(root.ls,root.rs);
}
void modify(int o,int c)
{
	if(!o)
		return;
	root.tag+=c;
	root.mx+=c,root.mi+=c;
	root.info+=c,root.sum+=root.siz*c;
}
void pushdown(int o)
{
	if(root.rev)
	{
		reverse(root.ls);
		reverse(root.rs);
		root.rev=0;
	}
	if(root.tag)
	{
		modify(root.ls,root.tag);
		modify(root.rs,root.tag);
		root.tag=0;
	}
}
void split(int &x,int &y,int k,int o)
{
	if(!o)
		x=y=0;
	else
	{
		pushdown(o);
		if(lson.siz<k)
		{
			x=o;
			split(root.rs,y,k-lson.siz-1,root.rs);
		}
		else
		{
			y=o;
			split(x,root.ls,k,root.ls);
		}
		pushup(o);
	}	
}
int merge(int x,int y)
{
	if(!x || !y)
		return x+y;
	pushdown(x),pushdown(y);
	if(treap[x].weight<treap[y].weight)
	{
		treap[x].rs=merge(treap[x].rs,y);
		pushup(x);
		return x;
	}
	else
	{
		treap[y].ls=merge(x,treap[y].ls);
		pushup(y);
		return y;
	}
}
void ins(int id,int val)
{
	rt[id]=merge(rt[id],newnode(val));
}
ll query_sum(int id,int l,int r)
{
	int x,y,z;
	split(x,y,l-1,rt[id]);
	split(y,z,r-l+1,y);
	ll ans=treap[y].sum;
	y=merge(y,z);
	rt[id]=merge(x,y);
	return ans;
}
int query_mx(int id,int l,int r)
{
	int x,y,z;
	split(x,y,l-1,rt[id]);
	split(y,z,r-l+1,y);
	int ans=treap[y].mx;
	y=merge(y,z);
	rt[id]=merge(x,y);
	return ans;
}
int query_mi(int id,int l,int r)
{
	int x,y,z;
	split(x,y,l-1,rt[id]);
	split(y,z,r-l+1,y);
	int ans=treap[y].mi;
	y=merge(y,z);
	rt[id]=merge(x,y);
	return ans;
}
void upd(int id,int l,int r,int c)
{
	int x,y,z;
	split(x,y,l-1,rt[id]);
	split(y,z,r-l+1,y);
	modify(y,c);
	y=merge(y,z);
	rt[id]=merge(x,y);
}
int siz[MAXN],mxson[MAXN],dep[MAXN],top[MAXN],fa[MAXN];
void dfs1(int u,int f)
{
	fa[u]=f;
	siz[u]=1;
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		if(v==f)
			continue;
		dep[v]=dep[u]+1;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[mxson[u]])
			mxson[u]=v;
	}
}
int cnt=0,tot[MAXN],rnk[MAXN],bel[MAXN];
void dfs2(int u,int tp)
{
	top[u]=tp,bel[u]=bel[tp];
	rnk[u]=++tot[bel[u]];
	ins(bel[u],0);
	if(mxson[u])
		dfs2(mxson[u],tp);
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		if(v==fa[u] || v==mxson[u])
			continue;
		bel[v]=++cnt;
		dfs2(v,v);
	}
}
void Increase(int x,int y,int c)
{
	if(dep[x]<dep[y])
		swap(x,y);
	while(top[x]!=top[y])
	{
		upd(bel[x],1,rnk[x],c);
		x=fa[top[x]];
	}
	if(dep[x]<dep[y])
		swap(x,y);
	upd(bel[x],rnk[y],rnk[x],c);
}
void Invert(int x,int y)
{
	int tx=x,ty=y;
	if(dep[x]<dep[y])
		swap(x,y);
	int tmp=0,a,b,c,d;
	while(top[x]!=top[y])
	{
		split(d,rt[bel[x]],rnk[x],rt[bel[x]]);
		tmp=merge(d,tmp);
		x=fa[top[x]];
	}
	if(dep[x]<dep[y])
		swap(x,y);
	int l=rnk[y],r=rnk[x];
	split(a,b,l-1,rt[bel[x]]);
	split(b,c,r-l+1,b);
	tmp=merge(b,tmp);
	reverse(tmp);
	x=tx,y=ty;
	if(dep[x]<dep[y])
		swap(x,y);
	while(top[x]!=top[y])
	{
		split(tmp,d,treap[tmp].siz-rnk[x],tmp);
		rt[bel[x]]=merge(d,rt[bel[x]]);
		x=fa[top[x]];
	}
	rt[bel[x]]=merge(a,merge(tmp,c));
}
int t=0;
ll Sum(int x,int y)
{
	ll res=0;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		res+=query_sum(bel[x],1,rnk[x]);
		x=fa[top[x]];
	}
	if(dep[x]<dep[y])
		swap(x,y);
	res+=query_sum(bel[x],rnk[y],rnk[x]);
	return res;
}
int Major(int x,int y)
{
	int res=-inf;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		res=max(res,query_mx(bel[x],1,rnk[x]));
		x=fa[top[x]];
	}
	if(dep[x]<dep[y])
		swap(x,y);
	res=max(res,query_mx(bel[x],rnk[y],rnk[x]));
	return res;
}
int Minor(int x,int y)
{
 	int res=inf;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		res=min(res,query_mi(bel[x],1,rnk[x]));
		x=fa[top[x]];
	}
	if(dep[x]<dep[y])
		swap(x,y);
	res=min(res,query_mi(bel[x],rnk[y],rnk[x]));
	return res;
}
int main()
{
	n=read(),m=read(),Root=read();
	for(int i=1;i<n;++i)
	{
		int u=read(),v=read();
		addedge(u,v);
		addedge(v,u);
	}
	dfs1(Root,0);
	bel[Root]=++cnt;
	dfs2(Root,Root);
	for(int i=1;i<=m;++i)
	{
		scanf("%s",op);
		int x=read(),y=read();
		if(op[0]=='I')
		{
			if(op[2]=='c') // Increase
			{
				int c=read();
				Increase(x,y,c);
			}
			else // Invert
				Invert(x,y);
		}
		else if(op[0]=='S') // Sum
			printf("%lld\n",Sum(x,y));
		else if(op[0]=='M')
		{
			if(op[1]=='a') // Major
				printf("%d\n",Major(x,y));
			else // Minor
				printf("%d\n",Minor(x,y));
		}
	}
	return 0;
}