题意
三种操作：
①区间增值
②某一个点换父亲
③求子树和
\(1\leq n\leq 100000\)
分析
Splay维护dfn序。
小结
（1）使用Splay，通常要在Splay的两端各添加一个虚拟节点，防止没有前驱和后继的情况。
（2）使用Splay的时候，要注意我们的key值是什么，与附加值进行区分。
（3）在父亲连接儿子的时候，如果我们也存父亲的情况，那么要记得儿子连向父亲。
（4）Splay是一种很难调试的数据结构，所以要掌握一种技巧：静态调试。
void Traver(int x) {
if (!x) return;
Traver(tr[x].c[0]);
printf("%d ",x);
Traver(tr[x].c[1]);
}（5）这类知道对应点位置，不知道其在树上位置的题，通常用Splay来解决。因为Treap要进行合并和分裂，需要知道在树上的位置。当然有一些处理方法：①记录父亲 ②相同权值不同化，记一个pair
（6）只有换根：分类讨论
定向link-cut：Splay维护dfn序
（7）把树变成链的三种序列：①每个出现一次 ②每个出现两次 ③每个出现度数次
代码
#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
#define per(i,a,b) for (int i=(a);i>=(b);i--)
#define lc tr[x].c[0]
#define rc tr[x].c[1]
#define pb push_back
typedef long long LL;
const int N=131072;
const int S=262144;
int n,m;
int w[N];
vector<int> g[N];
int tot;
int s[N],e[N];
struct Tree {
int c[2]; int fa;
int sz;
LL val,sum,tag;
Tree(int _lc=0,int _rc=0,int _fa=0,LL _val=0) {
c[0]=_lc,c[1]=_rc,fa=_fa;
sz=1;
val=_val; sum=_val; tag=0;
}
}tr[S];
int st[S],len;
LL rd(void) {
LL x=0,f=1; char c=getchar();
while (!isdigit(c)) {
if (c=='-') f=-1;
c=getchar();
}
while (isdigit(c)) {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
void DFS(int x,int fa) {
tot++; st[tot]=x; s[x]=tot;
rep(i,1,g[x].size()) {
int nx=g[x][i-1];
if (nx!=fa)
DFS(nx,x);
}
tot++; st[tot]=x; e[x]=tot;
}
void Pushup(int x) {
tr[x].sz=tr[lc].sz+tr[rc].sz+1;
tr[x].sum=tr[lc].sum+tr[rc].sum+tr[x].val;
}
void Clear(int x) {
if (tr[x].tag!=0) {
if (lc>0) {
tr[lc].val+=tr[x].tag;
tr[lc].tag+=tr[x].tag;
tr[lc].sum+=tr[x].tag*tr[lc].sz;
}
if (rc>0) {
tr[rc].val+=tr[x].tag;
tr[rc].tag+=tr[x].tag;
tr[rc].sum+=tr[x].tag*tr[rc].sz;
}
tr[x].tag=0;
}
}
void Rotate(int x) {
int y=tr[x].fa,z=tr[y].fa;
int l=!(tr[y].c[0]==x),r=l^1;
if (z>0) {
if (tr[z].c[0]==y)
tr[z].c[0]=x;
else tr[z].c[1]=x;
}
tr[x].fa=z; tr[y].fa=x;
if (tr[x].c[r]>0) tr[tr[x].c[r]].fa=y;
tr[y].c[l]=tr[x].c[r]; Pushup(y);
tr[x].c[r]=y; Pushup(x);
}
void Tsunami(int x) {
len=0; st[++len]=x;
for (int i=x;tr[i].fa>0;i=tr[i].fa)
st[++len]=tr[i].fa;
per(i,len,1) Clear(st[i]);
}
void Splay(int x,int rt=0) {
Tsunami(x);
while (tr[x].fa!=rt) {
int y=tr[x].fa,z=tr[y].fa;
if (z!=rt) {
if ((tr[y].c[0]==x)^(tr[z].c[0]==y))
Rotate(x);
else Rotate(y);
}
Rotate(x);
}
}
int Pre(int x) {
Splay(x);
x=lc; while (rc>0) x=rc;
return x;
}
int Nxt(int x) {
Splay(x);
x=rc; while (lc>0) x=lc;
return x;
}
LL Sum_Sub(int x) {
int l=s[x],r=e[x];
l=Pre(l),r=Nxt(r);
Splay(l); Splay(r,l);
return tr[tr[r].c[0]].sum;
}
void Add_Sub(int x,int y) {
int l=s[x],r=e[x];
l=Pre(l),r=Nxt(r);
Splay(l); Splay(r,l);
tr[tr[r].c[0]].val+=y;
tr[tr[r].c[0]].tag+=y;
tr[tr[r].c[0]].sum+=(LL)tr[tr[r].c[0]].sz*y;
Pushup(r); Pushup(l);
}
void Link_Cut(int x,int y) {
int l=s[x],r=e[x];
l=Pre(l),r=Nxt(r);
Splay(l); Splay(r,l);
int t=tr[r].c[0]; tr[r].c[0]=0; Pushup(r); Pushup(l);
int sy=s[y],ny=Nxt(sy);
Splay(sy); Splay(ny,sy);
tr[ny].c[0]=t; tr[t].fa=ny; Pushup(ny); Pushup(sy);
}
void Traver(int x) {
if (!x) return;
Traver(tr[x].c[0]);
printf("%d ",x);
Traver(tr[x].c[1]);
}
int main(void) {
#ifndef ONLINE_JUDGE
freopen("sd.in","r",stdin);
freopen("sd.out","w",stdout);
#endif
n=rd(),m=rd();
rep(i,1,n) w[i]=rd();
rep(i,1,n-1) {
int x=rd(),y=rd();
g[x].pb(y),g[y].pb(x);
}
DFS(1,-1);
rep(i,1,n) {
tr[s[i]]=Tree(0,s[i]+1,s[i]-1,w[i]);
tr[e[i]]=Tree(0,e[i]+1,e[i]-1,w[i]);
}
tr[0].sz=0;
tr[tot].c[1]=tot+1; tr[tot+1]=Tree(0,0,tot,0);
tr[tot+2]=Tree(0,1,0,0); tr[1].fa=tot+2;
per(i,tot,1) Pushup(i); Pushup(tot+2);
rep(i,1,m) {
int kd=rd(); int x,y; LL res;
switch (kd) {
case 1:
x=rd();
res=Sum_Sub(x)>>1;
printf("%lld\n",res);
break;
case 2:
x=rd(),y=rd();
Add_Sub(x,y);
break;
case 3:
x=rd(),y=rd();
Link_Cut(x,y);
break;
}
// Splay(1); Traver(1); printf("\n");
}
return 0;
}