题目概述

有一棵 $n$ 个点的点权树，刚开始根是 $1$ ，现在有 $q$ 次操作：

1. 把根换成 $x$ 。
2. 把 $LCA(x,y)$ 子树中节点的权值均加上 $w$ 。
3. 询问 $x$ 子树的权值和。

解题报告

Emm……学姿势学姿势……子树加子树求和直接DFS序+线段树，而换根实际上并不需要真的换根，只需要讨论节点与当前“根” $ro$ 的关系，树形维持不变（比如以 $1$ 为根）。Such as：

1. $x$ 就是 $ro$ ，那么直接对整棵树操作。
2. $x$ 不是 $ro$ 的祖先，那么直接对 $x$ 的子树操作就行了。
3. $x$ 是 $ro$ 的祖先，那么找到 $ro$ 最后一个不是 $x$ 的祖先 $fa$ ，对整棵树操作，对 $fa$ 的子树反操作。

示例程序

我可能脑子有问题，莫名其妙写了个LCT，实际上动态LCA也可以直接讨论得出。

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=300000;

int n,te,w[maxn+5],ro,ti,Lt[maxn+5],Rt[maxn+5];
int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5];
LL sum[(maxn<<2)+5],tag[(maxn<<2)+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
    if (l==r) return EOF;return *l++;
}
inline int readi(int &x){
    int tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return (lst=='-'?x=-tot:x=tot),Eoln(ch);
}
#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
#define Son(p) ((p)==son[fa[p]][1])
#define is_ro(p) ((p)!=son[fa[p]][0]&&(p)!=son[fa[p]][1])
namespace LCT{
    int son[maxn+5][2],fa[maxn+5];bool flip[maxn+5];
    inline void Rotate(int t){
        int p=fa[t],d=Son(t);son[p][d]=son[t][d^1];son[t][d^1]=p;
        if (!is_ro(p)) son[fa[p]][Son(p)]=t;
        if (son[p][d]) fa[son[p][d]]=p;fa[t]=fa[p];fa[p]=t;
    }
    inline void Addflip(int p) {swap(son[p][0],son[p][1]);flip[p]^=1;}
    inline void Pushdown(int p) {if (flip[p]) Addflip(son[p][0]),Addflip(son[p][1]),flip[p]=false;}
    inline void Splay(int p){
        static int stk[maxn+5],top;stk[top=1]=p;
        for (int i=p;!is_ro(i);i=fa[i]) stk[++top]=fa[i];
        while (top) Pushdown(stk[top--]);
        for (int pre=fa[p];!is_ro(p);Rotate(p),pre=fa[p])
            if (!is_ro(pre)) Rotate(Son(p)==Son(pre)?pre:p);
    }
    inline void Access(int p) {for (int lst=0;p;lst=p,p=fa[p]) Splay(p),son[p][1]=lst;}
    inline void Makero(int x) {Access(x);Splay(x);Addflip(x);}
    inline void Link(int x,int y) {Makero(x);fa[x]=y;}
    inline int LCA(int ro,int x,int y) {Makero(ro);Access(x);Access(y);Splay(x);return fa[x]?fa[x]:x;}
    inline int Lstfa(int ro,int x,int y){
        Makero(ro);Access(x);Access(y);Splay(x);
        while (Pushdown(x),son[x][0]) x=son[x][0];return x;
    }
}
void Dfs(int x,int pre=0) {Lt[x]=++ti;for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) Dfs(son[j],x);Rt[x]=ti;}
inline void Addtag(LL k,int l,int r,int p) {sum[p]+=k*(r-l+1);tag[p]+=k;}
inline void Pushdown(int l,int r,int p){
    LL now=tag[p];if (!now) return;tag[p]=0;int mid=l+(r-l>>1);
    Addtag(now,l,mid,p<<1);Addtag(now,mid+1,r,p<<1|1);
}
void Insert(int L,int R,int k,int l=1,int r=n,int p=1){
    if (R<l||r<L) return;if (L<=l&&r<=R) return Addtag(k,l,r,p);Pushdown(l,r,p);int mid=l+(r-l>>1);
    Insert(L,R,k,l,mid,p<<1);Insert(L,R,k,mid+1,r,p<<1|1);sum[p]=sum[p<<1]+sum[p<<1|1];
}
LL Ask(int L,int R,int l=1,int r=n,int p=1){
    if (R<l||r<L) return 0;if (L<=l&&r<=R) return sum[p];Pushdown(l,r,p);
    int mid=l+(r-l>>1);return Ask(L,R,l,mid,p<<1)+Ask(L,R,mid+1,r,p<<1|1);
}
inline void Update(int x,int w){
    if (LCT::LCA(1,ro,x)^x) Insert(Lt[x],Rt[x],w); else if (x==ro) Insert(1,n,w);
    else {int fa=LCT::Lstfa(1,ro,x);Insert(1,n,w);Insert(Lt[fa],Rt[fa],-w);}
}
inline LL Query(int x){
    if (LCT::LCA(1,ro,x)^x) return Ask(Lt[x],Rt[x]); else if (x==ro) return Ask(1,n);
    else {int fa=LCT::Lstfa(1,ro,x);return Ask(1,n)-Ask(Lt[fa],Rt[fa]);}
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    readi(n);readi(te);for (int i=1;i<=n;i++) readi(w[i]);
    for (int i=1,x,y;i<n;i++) readi(x),readi(y),Add(x,y),Add(y,x),LCT::Link(x,y);
    Dfs(ro=1);for (int i=1;i<=n;i++) Insert(Lt[i],Lt[i],w[i]);
    for (int t=1;t<=te;t++){
        int td,x,y,w;readi(td);readi(x);
        if (td==2) readi(y),readi(w),Update(LCT::LCA(ro,x,y),w);
        else if (td==3) printf("%lld\n",Query(x)); else ro=x;
    }
    return 0;
}