【BZOJ2631】tree

  裸的LCT。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned int uint;
const int maxn=100010,p=51061;

struct LCT
{
	struct Node
	{
		Node *c[2],*p,*lcp;
		int size;
		uint v,sum;
		uint tag_add,tag_mul;
		int tag_rev;
		int w() {return this==p->c[1];}
	}MEM[maxn],*ID[maxn],*Null;

	#define ls x->c[0]
	#define rs x->c[1]

	void Update(Node *x) {if (x==Null) return;x->sum=(ls->sum+rs->sum+x->v)%p;x->size=ls->size+rs->size+1;}
	void Mark_Rev(Node *x) {if (x==Null) return;swap(ls,rs);x->tag_rev^=1;}
	void Mark_Mul(Node *x,uint c) {if (x==Null) return;(x->v*=c)%=p;(x->sum*=c)%=p;(x->tag_add*=c)%=p;(x->tag_mul*=c)%=p;}
	void Mark_Add(Node *x,uint c) {if (x==Null) return;(x->v+=c)%=p;(x->sum+=c*x->size)%=p;(x->tag_add+=c)%=p;}

	void Push_Down(Node *x)
	{
		if (x==Null) return;
		if (x->tag_rev) Mark_Rev(ls),Mark_Rev(rs),x->tag_rev=0;
		if (x->tag_mul!=1) Mark_Mul(ls,x->tag_mul),Mark_Mul(rs,x->tag_mul),x->tag_mul=1;
		if (x->tag_add) Mark_Add(ls,x->tag_add),Mark_Add(rs,x->tag_add),x->tag_add=0;
	}

	void Rotate(Node *x)
	{
		Node *p=x->p;
		int w=x->w();
		Push_Down(p);Push_Down(x);
		x->lcp=p->lcp;p->lcp=Null;
		x->p=p->p;p->p->c[p->w()]=x;
		x->c[!w]->p=p;p->c[w]=x->c[!w];
		x->c[!w]=p;p->p=x;
		Update(p);
	}

	void Splay(Node *x,Node *top)
	{
		if (x==Null) return;
		Push_Down(x);
		while (x->p!=top)
		{
			if (x->p->p==top) {Rotate(x);break;}
			if (x->w()==x->p->w()) Rotate(x->p),Rotate(x);
				else Rotate(x),Rotate(x);
		}
		Update(x);
	}

	void Access(Node *x)
	{
		Node *pre=x,*v=Null;
		while (x!=Null)
		{
			Splay(x,Null);
			rs->lcp=x;
			rs->p=Null;
			rs=v;
			v->p=x;
			v->lcp=Null;
			Update(x);
			v=x;x=x->lcp;
		}
		Splay(pre,Null);
	}

	void Set_Root(Node *x) {Access(x);Mark_Rev(x);}

	void Init(int n)
	{
		Null=&MEM[0];
		for (int i=1;i<=n;i++) ID[i]=&MEM[i];
		for (int i=0;i<=n;i++) MEM[i].c[0]=MEM[i].c[1]=MEM[i].p=MEM[i].lcp=Null,MEM[i].v=MEM[i].sum=MEM[i].size=MEM[i].tag_mul=1;
		MEM[0].v=MEM[0].sum=MEM[0].size=0;
	}

	void Change_Add(int u,int v,int c)
	{
		Set_Root(ID[u]);
		Access(ID[v]);
		Mark_Add(ID[v],c);
	}
	
	void Change_Mul(int u,int v,int c)
	{
		Set_Root(ID[u]);
		Access(ID[v]);
		Mark_Mul(ID[v],c);
	}
	
	void Link(int u,int v)
	{
		Set_Root(ID[u]);
		Access(ID[v]);
		ID[u]->lcp=ID[v];
		Access(ID[u]);
	}
	
	void Cut(int u,int v)
	{
		Set_Root(ID[u]);
		Access(ID[v]);
		ID[v]->c[0]=ID[u]->p=Null;
		Update(ID[v]);
	}
	
	uint Sum(int u,int v)
	{
		Set_Root(ID[u]);
		Access(ID[v]);
		return ID[v]->sum;
	}
}T;

void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';}
char readchar() {char ch;while ((ch=getchar())!='+' && ch!='-' && ch!='*' && ch!='/');return ch;}
int n,q;

int main()
{
	read(n),read(q);
	T.Init(n);
	for (int i=1,x,y;i<n;i++) read(x),read(y),T.Link(x,y);
	while (q--)
	{
		char ctr=readchar();
		int u,v,c,u1,v1;
		read(u),read(v);
		if (ctr=='+') read(c),T.Change_Add(u,v,c);
		if (ctr=='-') read(u1),read(v1),T.Cut(u,v),T.Link(u1,v1);
		if (ctr=='*') read(c),T.Change_Mul(u,v,c);
		if (ctr=='/') printf("%d\n",T.Sum(u,v));
	}
	return 0;
}