支持子树操作的动态树(魔改LCT)

Y_B_X · 2021-06-27 09:51:51 · 个人记录

众所周知，LCT 可以算是最广为人知的动态树，

支持在 O(\log n) 的时间复杂度内进行对链上的大部分修改、查询操作
可它是否能支持对子树的修改、查询呢？

为了在之后更好证明各种维护子树的 LCT 的时间复杂度，

我首先证明一下 LCT 的时间复杂度(限于个人能力暂且忽略常数)：

在 LCT 的一颗 splay 中进行一次 local splay 的时间复杂度均摊为 O(\log(sz(\acute x))-\log(sz(x))+1)
其中 x 与 \acute x 分别代表伸展前后的节点，sz(x) 代表 x 节点在原树中的子树的大小。
证明可具体参见其他 splay 的时间复杂度证明，只是改了权值罢了
LCT$ 中 $access$ 的时间复杂度均摊为 $O(\log(n))
首先发现 \log(sz(\acute x))-\log(sz(x)) 在 access 中 splay 多次后时间叠加起来小于等于 \log(n)
所以只需证 access 经过链的个数均摊为 O(\log n):
定义势能函数为 LCT 中虚边与重边边（轻重链剖分得到的）重合的边(下称重虚边)的个数，
则一次 access 经过的重虚边会以 O(1) 的时间让势能 −1，时间总和均摊约去
经过的全部轻虚边会至多将势能增加轻虚边个数，即 O(\log(n))，同时经过轻虚边需 O(\log(n)),
加起来是 O(\log(n)) 的，得证。其他操作全基于 access ，同样是 O(\log(n)) 的均摊复杂度。

再转回我们的正题上，

对子树修改的关键，可以发现，最主要是需要对 LCT 中每个节点的虚儿子进行维护。

我们可以考虑对虚儿子再用一些数据结构来维护。

而影响虚儿子的操作有如下这些：

当一个节点被伸展时，它将会成为当前整颗 $splay$ 的父节点的一个虚儿子，而原先这颗 $splay$ 的根节点将被从它父节点的虚儿子中移除
$son[x][1]=y$ 这一段简短的代码意味着若 $y$ 节点存在，将其从 $x$ 的虚儿子中移除若 $son[x][1]$ 存在，将其加入 $x$ 的虚儿子中
只是将一个节点 $makeroot$ 然后加入另一个节点的虚儿子中

于是我们的数据结构只需支持添加、删除节点，同时能支持下放标记即可。
但由于此时标记是基于整棵树的，并不能在 splay 之前只对当前这颗 splay 下放标记

必须是从整棵 LCT 的根节点所在的 splay 的根开始传标记，在虚儿子间利用这个数据结构放标记

若每次 splay 前都这样全局 pushdall ，时间复杂度就 O(\log(n)^2) 了（~~比TopTree还慢~~）

减小时间复杂度的一个方法是只在 access 前全局 pushall，这个时间花费与 access 时间将等价

而这个数据结构怎么写才能尽可能缩小时间复杂度呢？

方法一

有一个很无脑且时间复杂度较大、常数特大、空间开销极大的方法。

就是直接对每个点开一个动态开点的线段树记录虚儿子。

单次加点、删点、下传标记稳稳要 O(\log(n))，且不能优化，还要写垃圾回收；

### 方法二由于原先 $LCT$ 就用了 $splay$，可以考虑再同时用 $splay$ 来维护虚儿子（这应该就是所谓的 $AAATree$ ）这个时候单次 $access$ 的时间不一定就是 $O(\log(n))$ ，主要原因是 $splay$ 在删除节点时需要找到它的前驱/后继旋到根再删，难以保证时间复杂度。理由如下：我们将维护虚儿子的 $splay$ 与 $LCT$ 中的 $splay$ 看在一起。同分析 $splay$ 的时间复杂度一样，我们定义势能函数 $\Phi=\sum\limits_{i=1}^{n}\log(sz(i))

其中sz(x) 代表 x 节点的子树的大小（包括两种 splay 中的节点）。

在 splay 时,设原先的根为 y ，y 在虚儿子的 splay 的前驱是 py，要旋转的节点是 x

设 y,py,x 旋到虚子树的 splay 的根后分别是 \acute y,\acute {py},\acute x 。（以下若无特殊声明皆为此意）

则在更改虚儿子（ y 旋到根，查前驱并旋到根再删 y，x 在 splay 上二分插入并旋到根）

与将 x 旋到当前 LCT 中的 splay 的根的摊还时间复杂度之和

=O(\log(sz(\acute y))-\log(sz(y))+\log(sz(\acute {py}))-\log(sz(py))+\log(sz(\acute x))-\log(sz(x)))+O(1)

由于 y 是当前 LCT 上的 splay 的根，且无论谁旋到虚子树的 splay 的根 sz() 不变

所以有 sz(y)\geq sz(x) 以及 sz(\acute y)=sz(\acute x)

因此摊还时间复杂度 \leq O(2*(\log(sz(\acute x))-\log(sz(x)))+\log(sz(\acute {py}))-\log(sz(py)))+O(1)

尽管 sz(\acute {py})=sz(\acute x) ，但由于 sz(py) 与 sz(x) 并不能得知谁大谁小，

故时间复杂度难以保证，单次 access 可被卡成至多 O(\log(n)^2)

于是 LCT 就真的不能做到如同 Top Tree 的 O(\log(n)) 的 access 时间了吗？

并非如此。

方法三

这种方法的启发主要还是参考了 Tarjan 的 Top Tree 论文。

我们在维护虚儿子的 splay 中换一种方式插入节点，够造成一个类似于 LeafyTree 的结构。

具体来说就是多用一些辅助节点构成整颗 splay ，

每个辅助节点必有两个儿子，表示原树虚儿子的“真实”节点都在叶子结点上。

这样整棵树的节点个数仍然是 O(n) 的。

若在删一个节点时，由于其没有左右儿子，直接连带他的父节点从整个 splay 中移除，

再将其原先父节点的父节点旋到根，更新一下即可，

而事实上更多时候我们只需要“替换”某一个节点的信息，同样直接改然后旋到根更新信息，十分方便。

而此时时间复杂度就在于旋到根的 splay 操作，这显然还是 O(\log(sz(\acute x))-\log(sz(x)))，

其中 \acute x 代表虚子树上 splay(x) 后的节点

那么对于 splay 操作，像上文一样设原先的根为 y ，当前要旋到根的点是 x。

则摊还时间是

O(\log(sz(\acute y))-\log(sz(y))+\log(sz(\acute x))-\log(sz(x))+1)

\leq O(2*(\log(sz(\acute x))-\log(sz(x)))+1)=O(\log(sz(\acute x))-\log(sz(x))+1)

1. $y$ 节点与 $son[x][1]$ 都存在：在维护虚儿子的 $splay$ 上 $y$ 的信息替换成 $son[x][1]$ 的信息，摊还时间为 $O(\log(sz(\acute y))-\log(sz(y))+1)\leq O(\log(sz(\acute x))-\log(x)+1)

y$ 节点不存在，$son[x][1]$ 存在：直接插入 $son[x][1]$ 到 $x$ 的虚儿子中，时间远小于 $O(\log(n))
这只能在 access 最开始出现此情况一次，插入不会成为复杂度瓶颈。

又由于链的个数均摊为 O(\log(n))，

我们可以得知单次 access 时间复杂度均摊为 O(\log(sz(root))-\log(sz(x))+\log(n))\leq O(\log(n))

最后提一个细节：为了让打标记不会一次打多个节点，

在实际实现时对每个点的虚儿子维护的 splay 时多加一个不动的根

给出三种方法的分别的代码(以CF916E为例，主要应为操作少，好写)：

方法一：(评测结果：第 56 个点 TLE，时间和空间都被卡)

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int N=1e5+10,M=8e6+10;
int n,m,tot,x,y,opt,rt=1;ll v,ans;
int root[N];
struct tree{int l,r;ll s,tag;int sz;}t[M];
queue<int> q;char ch;
void read(ll &x){bool f=0;x=0;ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();if(f)x=-x;}
void read(int &x){x=0;ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();}
void write(ll x){if(x>=10)write(x/10);putchar('0'+x%10);}
int anc[N],son[N][2],rev[N],size[N];ll sum[N],w[N],tag[N];
void init(int &k){t[k].s=t[k].l=t[k].r=0;}
void newnode(int &k){if(!q.empty())k=q.front(),q.pop();else k=++tot,init(k);}
void del(int &k){init(k);q.push(k);k=0;}
void pushup_(int k){t[k].s=t[t[k].l].s+t[t[k].r].s;t[k].sz=t[t[k].l].sz+t[t[k].r].sz;}
void tag_1(int k,ll v){t[k].s+=v*t[k].sz;t[k].tag+=v;}
void tag_(int x,ll v){sum[x]+=v*size[x];tag[x]+=v;w[x]+=v;if(root[x])tag_1(root[x],v);}
void pass(int x,int k){if(t[k].tag){tag_(x,t[k].tag);t[k].tag=0;}}
void copy(int k,int x){t[k].s=sum[x];t[k].sz=size[x];}
void pushdown1(int k){
    if(t[k].tag){
        if(t[k].l)tag_1(t[k].l,t[k].tag);
        if(t[k].r)tag_1(t[k].r,t[k].tag);
        t[k].tag=0;
    }
}
void update(int l,int r,int &k,int pos,int b){
    if(!k)newnode(k);
    if(l==r){if(b)copy(k,l);else del(k);return;}
    int mid=(l+r)>>1;pushdown1(k);
    if(pos<=mid)update(l,mid,t[k].l,pos,b);
    else update(mid+1,r,t[k].r,pos,b);
    pushup_(k);if(!b&&!t[k].s)del(k);
}
void pushdown1(int l,int r,int k,int pos){
    if(l==r)return pass(l,k);
    int mid=(l+r)>>1;pushdown1(k);
    if(pos<=mid)pushdown1(l,mid,t[k].l,pos);
    else pushdown1(mid+1,r,t[k].r,pos);
}
void rev_(int x){rev[x]^=1;swap(son[x][0],son[x][1]);}
bool p(int x){return son[anc[x]][1]==x;}
bool isroot(int x){return son[anc[x]][0]!=x&&son[anc[x]][1]!=x;}
void fix(int x){
    if(!x)return;
    sum[x]=sum[son[x][0]]+sum[son[x][1]]+w[x]+t[root[x]].s;
    size[x]=size[son[x][0]]+size[son[x][1]]+1+t[root[x]].sz;
}
int rotate(int x){int y=anc[x],xx=anc[y];bool b=p(x),bb=p(y);
    anc[x]=xx;if(!isroot(y))son[xx][bb]=x;son[y][b]=son[x][b^1];
    anc[son[x][b^1]]=y;son[x][b^1]=y;anc[y]=x;fix(y);fix(x);fix(xx);
}
void pushdown(int x){
    if(rev[x]){
        if(son[x][0])rev_(son[x][0]);
        if(son[x][1])rev_(son[x][1]);
        rev[x]=0;
    }
    if(tag[x]){
        if(son[x][0])tag_(son[x][0],tag[x]);
        if(son[x][1])tag_(son[x][1],tag[x]);
        tag[x]=0;
    }
}
void pushall_(int x){
    if(!isroot(x))pushall_(anc[x]);
    else if(anc[x]){pushall_(anc[x]);pushdown1(1,n,root[anc[x]],x);}
    pushdown(x);
}
void pushall(int x){
    if(!isroot(x))pushall(anc[x]);
    pushdown(x);
}
int getroot(int x){if(isroot(x))return x;return getroot(anc[x]);};
void splay(int x){pushall(x);int y=getroot(x);
    if(anc[y])update(1,n,root[anc[y]],y,0),update(1,n,root[anc[y]],x,1);
    for(int i=anc[x];i=anc[x],!isroot(x);rotate(x)){
        if(!isroot(i)){if(p(x)==p(i))rotate(i);else rotate(x);}
    }
}
int access(int x){pushall_(x);int y=0;
    for(;x;y=x,x=anc[x]){
        splay(x);
        if(y)update(1,n,root[x],y,0);
        if(son[x][1])update(1,n,root[x],son[x][1],1);
        son[x][1]=y;fix(x);
    }
    return y;
}
int findrt(int x){
    pushdown(x);
    while(son[x][0])pushdown(x=son[x][0]);
    return splay(x),x;
}
void makeroot(int x){access(x);splay(x);rev_(x);}
void split(int x,int y){makeroot(x);access(y);splay(y);}
void link(int x,int y){split(x,y);anc[x]=y;update(1,n,root[y],x,1);fix(y);}
void subtree_add(int x,ll v){
    split(rt,x);
    sum[x]+=v*(t[root[x]].sz+1);w[x]+=v;
    tag_1(root[x],v);
}
int lca(int x,int y){
    makeroot(rt);
    access(x);return access(y);
}
main(){
    read(n),read(m);
    for(int i=1;i<=n;i++)read(w[i]),fix(i);
    for(int i=1;i<n;i++)read(x),read(y),link(x,y);y=0;
    while(m--){
        read(opt),read(x);
        if(opt==1)rt=x;
        if(opt==2)read(y),read(v),subtree_add(lca(x,y),v);
        if(opt==3){
            split(rt,x);
            ans=t[root[x]].s+w[x];
            if(ans<0)putchar('-'),write(-ans);
            else write(ans);
            putchar('\n');
        }
    }
}

方法二 (评测结果：AC(1.13\min))

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int n,m,x,y,opt,root=1;ll v,ans;
int son[N][2],anc[N],sz[N],rt[N],rev[N];ll sum[N],w[N],tag[N];
void tag_(int x,ll v);
struct Splay{
    int son[N<<1][2],anc[N<<1],sz[N<<1],wsz[N<<1];ll sum[N<<1],wsum[N<<1],tag[N<<1];
    void tag_1(int x,ll v){
        sum[x]+=sz[x]*v;
        wsum[x]+=wsz[x]*v;
        tag[x]+=v;
        if(x<=n)tag_(x,v);
    }
    void pushdown(int x){
        if(tag[x]){
            if(son[x][0])tag_1(son[x][0],tag[x]);
            if(son[x][1])tag_1(son[x][1],tag[x]);
            tag[x]=0;
        }
    }
    void pushall(int x){
        if(anc[x])pushall(anc[x]);
        pushdown(x);
    }
    void fix(int x){if(!x)return;sum[x]=sum[son[x][0]]+sum[son[x][1]]+wsum[x];
        sz[x]=sz[son[x][0]]+sz[son[x][1]]+wsz[x];
    }
    bool p(int x){return son[anc[x]][1]==x;}
    void rotate(int x){int y=anc[x],xx=anc[y];bool b=p(x),bb=p(y);
        anc[x]=xx;if(xx)son[xx][bb]=x;son[y][b]=son[x][b^1];
        anc[son[x][b^1]]=y;son[x][b^1]=y;anc[y]=x;fix(y);fix(x);fix(xx);
    }
    void splay(int x,int rt){pushall(x);
        for(int i=anc[x];i=anc[x],i!=rt;rotate(x))if(anc[i]!=rt){
            if(p(x)==p(i))rotate(i);else rotate(x);
        }
    }
    void ins(int x,int y,ll sum_,int sz_){
        wsum[x]=sum_,wsz[x]=sz_;fix(x);int tmp=rt[y],f=0;
        while(1){
            if(!tmp){son[f][x>f]=x;anc[x]=f;fix(f);return splay(x,rt[y]);}
            pushdown(tmp);
            f=tmp;tmp=son[tmp][x>tmp];
        }
    }
    void clear(int x){wsz[x]=sz[x]=wsum[x]=sum[x]=son[x][0]=son[x][1]=anc[x]=tag[x]=0;}
    int pre(int x){x=son[x][0];while(son[x][1])x=son[x][1];return x;}
    void del(int x,int y){
        splay(x,rt[y]);
        if(!son[x][0]&&!son[x][1])return clear(x),son[rt[y]][0]=0,fix(rt[y]),void();
        int b=!son[x][0]?0:!son[x][1]?1:-1;
        if(~b)return anc[son[rt[y]][0]=son[x][b^1]]=rt[y],clear(x),fix(rt[y]),void();
        int xx=pre(x);splay(xx,rt[y]);son[xx][1]=son[x][1];
        anc[son[x][1]]=xx;clear(x);fix(xx);fix(rt[y]);
    }
}S;
void tag_(int x,ll v){sum[x]+=v*sz[x];w[x]+=v;tag[x]+=v;S.tag_1(rt[x],v);}
void rev_(int x){rev[x]^=1;son[x][0]^=son[x][1]^=son[x][0]^=son[x][1];}
bool p(int x){return son[anc[x]][1]==x;}
bool isroot(int x){return son[anc[x]][0]!=x&&son[anc[x]][1]!=x;}
void fix(int x){
    if(!x)return;
    sum[x]=sum[son[x][0]]+sum[son[x][1]]+w[x]+S.sum[rt[x]];
    sz[x]=sz[son[x][0]]+sz[son[x][1]]+1+S.sz[rt[x]];
}
void pushdown(int x){
    if(rev[x]){if(son[x][0])rev_(son[x][0]);
    if(son[x][1])rev_(son[x][1]);rev[x]=0;}
    if(tag[x]){if(son[x][0])tag_(son[x][0],tag[x]);
    if(son[x][1])tag_(son[x][1],tag[x]);tag[x]=0;}
}
void pushall(int x){
    if(!isroot(x))pushall(anc[x]);
    pushdown(x);
}
void pushall_(int x){
    if(!isroot(x))pushall_(anc[x]);
    else if(anc[x]){pushall_(anc[x]);S.pushall(x);}
    pushdown(x);
}
void rotate(int x){int y=anc[x],xx=anc[y];bool b=p(x),bb=p(y);
    anc[x]=xx;if(!isroot(y))son[xx][bb]=x;son[y][b]=son[x][b^1];
    anc[son[x][b^1]]=y;son[x][b^1]=y;anc[y]=x;fix(y);fix(x);fix(xx);
}
int findrt(int x){if(!isroot(x))return findrt(anc[x]);return x;}
void splay(int x){pushall(x);int y=findrt(x);
    if(anc[y]&&x!=y)S.del(y,anc[y]),S.ins(x,anc[y],sum[y],sz[y]);
    for(int i=anc[x];i=anc[x],!isroot(x);rotate(x))
        if(!isroot(i)){if(p(i)==p(x))rotate(i);else rotate(x);}
}
int access(int x){
    int y=0;pushall_(x);
    for(;x;y=x,x=anc[x]){
        splay(x);
        if(y)S.del(y,x);
        if(son[x][1])S.ins(son[x][1],x,sum[son[x][1]],sz[son[x][1]]);
        son[x][1]=y;fix(x);
    }
    return y;
}
void makeroot(int x){access(x);splay(x),rev_(x);}
void split(int x,int y){makeroot(x),access(y),splay(y);}
void link(int x,int y){split(x,y);anc[x]=y;S.ins(x,y,sum[x],sz[x]);fix(y);}
void subtree_add(int x,ll v){
    split(root,x);
    sum[x]+=v*(S.sz[rt[x]]+1);w[x]+=v;
    S.tag_1(rt[x],v);
}
int lca(int x,int y){
    makeroot(root);
    access(x);return access(y);
}
main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&w[i]),fix(i),rt[i]=i+n;
    for(int i=1;i<n;i++)scanf("%d%d",&x,&y),link(x,y);
    while(m--){
        scanf("%d%d",&opt,&x);
        if(opt==1)root=x;
        if(opt==2)scanf("%d%lld",&y,&v),subtree_add(lca(x,y),v);
        if(opt==3){
            split(root,x);
            ans=sum[son[x][1]]+S.sum[rt[x]]+w[x];
            printf("%lld\n",ans);
        }
    }
}

方法三(评测结果：AC(54.87s))

#define ll long long
using namespace std;
const int N=1e5+10;
int n,m,x,y,opt,root=1;ll v,ans;
int son[N][2],anc[N],sz[N],rt[N],rev[N];ll sum[N],w[N],tag[N];
void tag_(int x,ll v);
struct leafy_Splay{
    int son[N<<2][2],anc[N<<2],sz[N<<2],wsz[N<<2],tot;ll sum[N<<2],wsum[N<<2],tag[N<<2];
    queue<int> q;
    void tag_1(int x,ll v){
        sum[x]+=sz[x]*v;
        wsum[x]+=wsz[x]*v;
        tag[x]+=v;
        if(x<=n)tag_(x,v);
    }
    void fix(int x){if(!x)return;sum[x]=sum[son[x][0]]+sum[son[x][1]]+wsum[x];
        sz[x]=sz[son[x][0]]+sz[son[x][1]]+wsz[x];}
    bool p(int x){return son[anc[x]][1]==x;}
    int newnode(){if(!q.empty()){int x=q.front();return q.pop(),x;}return ++tot;}
    void pushdown(int x){
        if(tag[x]){
            if(son[x][0])tag_1(son[x][0],tag[x]);
            if(son[x][1])tag_1(son[x][1],tag[x]);
            tag[x]=0;
        }
    }
    void pushall(int x){
        if(anc[x])pushall(anc[x]);
        pushdown(x);
    }
    void rotate(int x){int y=anc[x],xx=anc[y];bool b=p(x),bb=p(y);
        anc[x]=xx;if(xx)son[xx][bb]=x;son[y][b]=son[x][b^1];
        anc[son[x][b^1]]=y;son[x][b^1]=y;anc[y]=x;fix(y);fix(x);fix(xx);
    }
    void splay(int x,int y){pushall(x);
        for(int i=anc[x];i=anc[x],i!=y;rotate(x))
            if(anc[i]!=y){if(p(x)==p(i))rotate(i);else rotate(x);}
    }
    void split(int x,int y){
        int a=0;
        if(anc[x]!=rt[y])splay(a=anc[x],rt[y]);
        if(anc[x]!=a&&anc[x]!=rt[y])splay(anc[x],a);
        pushdown(anc[x]);pushdown(x);
    }
    void ins(int x,int y,ll sum_,int sz_){
        wsum[x]=sum_;wsz[x]=sz_;fix(x);int tmp=rt[y],f=0;pushdown(tmp);
        if(!son[rt[y]][0])return anc[son[rt[y]][0]=x]=rt[y],fix(rt[y]);
        while(1){
            if(!tmp){
                tmp=newnode();anc[son[anc[f]][p(f)]=tmp]=anc[f];
                son[tmp][x>f]=x;anc[x]=tmp;
                son[tmp][x<f]=f;anc[f]=tmp;
                fix(f);fix(tmp);fix(anc[tmp]);
                return splay(tmp,rt[y]);
            }
            pushdown(tmp);
            f=tmp;tmp=son[tmp][x>tmp];
        }
    }
    void clear(int x){wsz[x]=sz[x]=wsum[x]=sum[x]=son[x][0]=son[x][1]=anc[x]=0;
                if(x>(n<<1))q.push(x);}
    void del(int x,int y){
        if(anc[x]==rt[y])return son[rt[y]][0]=0,fix(rt[y]),clear(x);
        int yy=anc[x],xx=anc[yy];bool b=p(x),bb=p(yy);
        if(xx==rt[y]){
            anc[son[rt[y]][0]=son[yy][b^1]]=rt[y];
            clear(x),clear(yy),fix(rt[y]);
            return;
        }
        anc[son[xx][p(yy)]=son[yy][b^1]]=xx;
        clear(x);clear(yy);fix(xx);splay(xx,rt[y]);fix(rt[y]);
    }
    void display(int x,int xx,ll sum_,int sz_,int y){
        wsum[xx]=sum_;wsz[xx]=sz_;fix(xx);int yy=anc[x];
        anc[son[yy][p(x)]=xx]=yy;clear(x);fix(yy);
                if(yy!=rt[y])splay(yy,rt[y]);fix(rt[y]);
    }
}S;
void rev_(int x){rev[x]^=1;son[x][0]^=son[x][1]^=son[x][0]^=son[x][1];}
void tag_(int x,ll v){sum[x]+=v*sz[x];w[x]+=v;tag[x]+=v;S.tag_1(rt[x],v);}
bool p(int x){return son[anc[x]][1]==x;}
bool isroot(int x){return son[anc[x]][0]!=x&&son[anc[x]][1]!=x;}
void fix(int x){
    if(!x)return;
    sum[x]=sum[son[x][0]]+sum[son[x][1]]+w[x]+S.sum[rt[x]];
    sz[x]=sz[son[x][0]]+sz[son[x][1]]+1+S.sz[rt[x]];
}
void pushdown(int x){
    if(rev[x]){if(son[x][0])rev_(son[x][0]);
    if(son[x][1])rev_(son[x][1]);rev[x]=0;}
    if(tag[x]){if(son[x][0])tag_(son[x][0],tag[x]);
    if(son[x][1])tag_(son[x][1],tag[x]);tag[x]=0;}
}
void pushall(int x){
    if(!isroot(x))pushall(anc[x]);
    pushdown(x);
}
void pushall_(int x){
    if(!isroot(x))pushall_(anc[x]);
    else if(anc[x]){
        pushall_(anc[x]);
        S.pushall(x);
    }
    pushdown(x);
}
void rotate(int x){int y=anc[x],xx=anc[y];bool b=p(x),bb=p(y);
    anc[x]=xx;if(!isroot(y))son[xx][bb]=x;son[y][b]=son[x][b^1];
    anc[son[x][b^1]]=y;son[x][b^1]=y;anc[y]=x;fix(y);fix(x);fix(xx);
}
int findrt(int x){if(isroot(x))return x;return findrt(anc[x]);}
void splay(int x){pushall(x);int y=findrt(x);
    if(anc[y]&&x!=y)S.display(y,x,sum[y],sz[y],anc[y]);
    for(int i=anc[x];i=anc[x],!isroot(x);rotate(x)){
        if(!isroot(i)){if(p(i)==p(x))rotate(i);else rotate(x);}
    }
}
int access(int x){
    int y=0;pushall_(x);
    for(;x;y=x,x=anc[x]){
        splay(x);
        if(y&&son[x][1])S.display(y,son[x][1],sum[son[x][1]],sz[son[x][1]],x);
        else if(!y&&son[x][1])S.ins(son[x][1],x,sum[son[x][1]],sz[son[x][1]]);
        else if(y&&!son[x][1])S.del(y,x);
        son[x][1]=y;fix(x);
    }
    return y;
}
void makeroot(int x){access(x);splay(x),rev_(x);}
void split(int x,int y){makeroot(x),access(y),splay(y);}
void link(int x,int y){split(x,y);anc[x]=y;S.ins(x,y,sum[x],sz[x]);fix(y);}
void subtree_add(int x,ll v){
    split(root,x);
    sum[x]+=v*(S.sz[rt[x]]+1);w[x]+=v;
    S.tag_1(rt[x],v);
}
int lca(int x,int y){
    makeroot(root);access(x);return access(y);
}
main(){
    scanf("%d%d",&n,&m);S.tot=n<<1;
    for(int i=1;i<=n;i++)scanf("%lld",&w[i]),fix(i),rt[i]=i+n,S.fix(i);
    for(int i=1;i<n;i++)scanf("%d%d",&x,&y),link(x,y);
    while(m--){
        scanf("%d%d",&opt,&x);
        if(opt==1)root=x;
        if(opt==2)scanf("%d%lld",&y,&v),subtree_add(lca(x,y),v);
        if(opt==3){
            split(root,x);
            ans=sum[son[x][1]]+S.sum[rt[x]]+w[x];
            printf("%lld\n",ans);
        }
    }
}

目前本人已实现过的题：

CF916E Jamie and Tree

P3979 遥远的国度

P3384 【模板】轻重链剖分/树链剖分

P5649 Sone1

SP16580 QTREE7

P6589 关系树（吊打标算）

虽然实现起来十分好写，但遗憾的是常数确实要比 \text{TopTree} 大将近 1.5 倍。