学步园

题意就是将BZOJ1798的数列的操作改成了树的操作。大体相似，用 Link -Cut-Tree 维护。

貌似细节不少的样子呢……一定要细心……当年这道题调了好久的说……//其实是我太渣了

update 函数里忘记了加 maintain(x) 的错误 QAQ

同时这也是我写的少数数组版代码之一//数组写成这个样子ch[fa[f]][check(f)]也是真心不爽嗯

下面是我的数组版代码~~

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define mod 51061
#define N 100005
int n,q,ch[N][2],fa[N],rev[N];
unsigned int val[N],size[N],sum[N],mul[N],add[N];
inline bool root(int x)
{
	return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;
}
inline bool check(int x)
{
	return ch[fa[x]][1]==x;
}
void reverse(int x)
{
	rev[x]^=1;
	rev[ch[x][0]]^=1;
	rev[ch[x][1]]^=1;
	swap(ch[x][0],ch[x][1]);
}
void calc(int x,unsigned int y,unsigned int z)
{
	val[x]=(val[x]*y+z)%mod;
	sum[x]=(sum[x]*y+size[x]*z)%mod;
	mul[x]=(mul[x]*y)%mod;
	add[x]=(add[x]*y+z)%mod;
}
void pushdown(int x)
{
	if(!root(x))
		pushdown(fa[x]);
	if(rev[x])
		reverse(x);
	if(ch[x][0]) calc(ch[x][0],mul[x],add[x]);
	if(ch[x][1]) calc(ch[x][1],mul[x],add[x]);
	mul[x]=1,add[x]=0;
}
void maintain(int x)
{
	sum[x]=(sum[ch[x][0]]+sum[ch[x][1]]+val[x])%mod;
	size[x]=(size[ch[x][0]]+size[ch[x][1]]+1)%mod;
}
void rotate(int x)
{
	int f=fa[x],d=!check(x);
	ch[f][d^1]=ch[x][d]; fa[ch[x][d]]=f; ch[x][d]=f;
	if(!root(f)) ch[fa[f]][check(f)]=x;
	fa[x]=fa[f]; fa[f]=x;
	maintain(f);maintain(x);
}
void splay(int x)
{
	pushdown(x);
	while(!root(x))
	{
		if(!root(fa[x]))
			check(fa[x])^check(x)?rotate(x):rotate(fa[x]);
		rotate(x);
	}
}
void access(int x)
{
	int y=0;
	while(x) splay(x),ch[x][1]=y,maintain(x),x=fa[y=x];
}
void makeroot(int x)
{
	access(x);splay(x);
	rev[x]^=1;
}
void link(int x,int y)
{
	makeroot(x);
	fa[x]=y;
}
void cut(int x,int y)
{
	makeroot(x);
	access(y);splay(y);
	ch[y][0]=fa[x]=0;
}
int main()
{
	cin>>n>>q;
	for(int i=1;i<=n;i++)
		val[i]=size[i]=sum[i]=mul[i]=1;
	for(int x,y,i=1;i<n;i++)
		scanf("%u%u",&x,&y),
		link(x,y);
	while(q--)
	{
		char ch[5];int u,v,x,y;
		scanf("%s",ch);
		if(ch[0]=='+')
		{
			scanf("%d%d%d",&u,&v,&x);
			makeroot(u);
			access(v);splay(v);
			calc(v,1,x);
		}
		else if(ch[0]=='-')
		{
			scanf("%d%d%d%d",&u,&v,&x,&y);
			cut(u,v);link(x,y);
		}
		else if(ch[0]=='*')
		{
			scanf("%d%d%d",&u,&v,&x);
			makeroot(u);
			access(v);splay(v);
			calc(v,x,0);
		}
		else if(ch[0]=='/')
		{
			scanf("%d%d",&u,&v);
			makeroot(u);
			access(v);splay(v);
			printf("%u\n",sum[v]);
		}
	}
	return 0;
}