题目大意
给一棵n个带点权节点(初始为0)的树 有三种操作: 1，对一条路径上的点的点权全部增加一个数 2，求一条路径上的点的点权和 3，对一条路径进行轮换(假如路径为a_1~a_k则a_1–>a_2,a_2–>a_3….a_k–>a_1)
容易想到用lct维护，轮换操作可以直接把左端点接到右端点的右儿子处，但这样会改变树的形态，具体实现就是把权值和形态分开来维护，维护树的形态的lct中，每个splay的root记录对应的权值splay的某一个点(不一定是该splay的root，我们可以访问的时候在跳到root，同时更新一下即可)
代码
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define ll long long
#define l tree[x][0]
#define r tree[x][1]
using namespace std;
int w;
char ch;
inline int read(){
w=
0;
for(ch=getchar();ch<
'0'||ch>
'9';ch=getchar());
for(;ch>=
'0'&ch<=
'9';ch=getchar())w=w*
10+ch-
48;
return w;
}
const int maxn=
1e5+
5;
int i,j,n,q[maxn],cnt,k[maxn],next[maxn*
2],g[maxn*
2],num,qs;
struct Tsplay{
int tree[maxn][
2],fa[maxn],val[maxn],s[maxn],tag[maxn];
ll sum[maxn];
bool bz[maxn];
bool pd(
int x) {
return tree[fa[x]][
1]==x;}
void update(
int x){
s[x]=s[l]+s[r]+
1,sum[x]=val[x];
if (l) sum[x]+=sum[l];
if (r) sum[x]+=sum[r];
}
void ins(
int x,
int v){val[x]=sum[x]=v,s[x]=
1;}
void add(
int x,
int v) {
if (x) tag[x]+=v,val[x]+=v,sum[x]+=(ll)s[x]*v;}
void re(
int x){
if (x) swap(l,r),bz[x]^=
1;}
void clear(
int x){
if (bz[x]) re(l),re(r),bz[x]=
0;
if (tag[x]) add(l,tag[x]),add(r,tag[x]),tag[x]=
0;
}
void chu(
int x){
if (fa[x]) chu(fa[x]);
clear(x);
}
void rotate(
int x){
int y=fa[x],z=pd(x),z1=pd(y);
if (fa[x]=fa[y]) tree[fa[x]][z1]=x;
if (tree[y][z]=tree[x][z^
1]) fa[tree[y][z]]=y;
fa[y]=x,tree[x][z^
1]=y;
update(y);
}
void splay(
int x){
chu(x);
for(;fa[x];){
int y=fa[x];
if (fa[y]) {
if (pd(x)==pd(y)) rotate(y);
else rotate(x);
}rotate(x);
}update(x);
}
int root(
int &x) {
for(;fa[x];x=fa[x]);
return x;}
int kth(
int &x,
int k){
for(;;){
clear(x);
if (s[l]+
1==k)
return x;
if (s[l]+
1>k) x=l;
else k-=s[l]+
1,x=r;
}
}
void turn(
int x){
int ls=x,rs=x;
kth(ls,
1),splay(ls),kth(rs=ls,s[ls]);
int now=tree[ls][
1];
fa[now]=
0,tree[ls][
1]=
0;
splay(rs);
tree[rs][
1]=ls,fa[ls]=rs;
update(rs);
}
}val;
struct Tlct{
int s[maxn],fa[maxn],tfa[maxn],tree[maxn][
2],rt[maxn];
bool bz[maxn];
bool pd(
int x) {
return tree[fa[x]][
1]==x;}
void update(
int x){s[x]=s[l]+s[r]+
1;}
void ins(
int x,
int f,
int v){rt[x]=x,s[x]=
1,tfa[x]=f,val.ins(x,v);}
void re(
int x){
if (x) swap(l,r),bz[x]^=
1;}
void clear(
int x){
if (bz[x]) re(l),re(r),bz[x]=
0;}
void chu(
int x){
if (fa[x]) chu(fa[x]);
clear(x);
}
void rotate(
int x){
int y=fa[x],z=pd(x),z1=pd(y);
if (fa[x]=fa[y]) tree[fa[x]][z1]=x;
if (tree[y][z]=tree[x][z^
1]) fa[tree[y][z]]=y;
rt[x]=rt[y],tfa[x]=tfa[y],rt[y]=tfa[y]=
0;
fa[y]=x,tree[x][z^
1]=y;
update(y);
}
void splay(
int x){
chu(x);
for(;fa[x];){
int y=fa[x];
if (fa[y]) {
if (pd(x)==pd(y)) rotate(y);
else rotate(x);
}rotate(x);
}update(x);
}
void access(
int x){
int last=
0,y,y2,x2;
for(;x;last=x,x=tfa[x]){
splay(x);
x2=val.root(rt[x]);
val.kth(x2,s[l]+
1),val.splay(rt[x]=x2);
y=tree[x][
1];
if (y){
tree[x][
1]=
0,fa[y]=
0,tfa[y]=x;
rt[y]=val.tree[x2][
1],val.fa[rt[y]]=
0,val.tree[x2][
1]=
0;
}
if (last){
tree[x][
1]=last,fa[last]=x,tfa[last]=
0;
y2=val.root(rt[last]);
val.tree[x2][
1]=y2,val.fa[y2]=x2;
}
val.update(x2),update(x);
}
}
void makeroot(
int x){access(x),splay(x),re(x),val.re(rt[x]);}
void path(
int x,
int y){makeroot(x),access(y);}
}lct;
void add(
int x,
int y){
next[++num]=k[x],k[x]=num,g[num]=y;
next[++num]=k[y],k[y]=num,g[num]=x;
}
char c[
10];
void pint(ll x){
if (x>=
10) pint(x/
10);
putchar(x%
10+
48);
}
void dfs(
int x,
int y){
lct.ins(x,y,
0);
for(
int i=k[x];i;i=next[i]){
int gg=g[i];
if (gg!=y) dfs(gg,x);
}
}
int main(){
freopen(
"shift.in",
"r",stdin);
freopen(
"shift.out",
"w",stdout);
n=read();
fo(i,
1,n-
1)add(read(),read());
dfs(
1,
0);
qs=read();
fo(i,
1,qs){
scanf(
"%s",c+
1);
int y=read(),x=read();
lct.path(x,y);
int ro=val.root(lct.rt[y]);
if (c[
1]==
'A'){
int z=read();
val.add(ro,z);
}
else if (c[
1]==
'Q') pint(val.sum[ro]),
putchar(
'\n');
else if (x!=y)val.turn(ro);
}
}
