LCT 维护动态带权重剖P9158 题解（2023 激励计划评分 10）

· · 题解

Part1 前言

省选前一直想改这道题，一直不敢，结果现在国赛模拟搬原题强制落实，被我两个小时场切了。

启示：数据结构题还是场切更有意思。

最近的国赛模拟频繁地出现 LCT 或 Top Tree（无一例外都场切了），可能会直接导致我重新开始研究 Top Tree，毕竟我又没有 D/E 类名额。

Part2 问题转化

发现将一个节点与其儿子依次合并不好做，将这棵树重构。

每次将 A_x 与 A_y 合并时，新建一个节点，左儿子为 x，右儿子为 y。

注意这时 x 会变成新建的节点，同时记录每一个节点子树最后的合并结果为 mst_x，查询时就是从 mst_x 开始往下跳关于 a_x 的带权重链。

Part3 两个操作

WBTT 这篇文章讲得很清楚，反正我都是学 zx2003 的。

这篇文章里讲了两个操作，access 和 drop，我们每次更改节点 x 的权值时，先对 x access，即强制将其到根路径上的边变为重边。

然后进行 drop，即将不合法的重边变为轻边，具体地，记录 lt_x 表示节点 x 的重儿子带权 size 减去轻儿子带权 size，若 lt_x\le 0，则可能需要抖落，这样的边最多有 O(\log V) 条。

至于如何动态维护 lt_x，只要在 access 之后链加就行了。

Part4 一些细节

求答案时需要向下跳重链，起初我想用倍增维护（参考 CSP-S 2019 树的重心），但这样是错误的，我白白浪费了好多时间。

事实上，这里需要记录 cl_x 表示 x 往下跳到底的答案，在带权轻重边切换时，假设是 x 的重儿子变为 y，我们先求出 cl_y，再从 x 往上（二分）跳重链，将这段重链节点的 cl 赋值为 cl_y。

因为每次切换 O(\log n)，每次最多 O(\log V) 次切换，所以总时间复杂度 O(n+q\log n\log V)，空间 O(n)。

Part5 后记

希望我可以从本题衍生出 WBTT 的考场可写作实现方式。

希望 Top Tree 文化能够一直传递下去。

才 2023 年，有的是希望。

Upd：本题并不能衍生出 WBTT 的实现方式，因为那比这个要复杂许多，但我已经学会了复杂度严格、支持 Link-Cut 的 WBTT，却依旧无法做到 考场可写作。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
using ll=long long;
ll a[N],sm[N];
int n,q,rt,cnt,L[N],R[N],fa[N];
int mst[N],d[N];
vector<int>lk[N];
ll lt[N],mn[N],tg[N];
int cl[N],ctg[N];
int lc[N],sl[N];//lc[x]=1->x is'nt wtson
int t[N][2],f[N];
#define ls t[x][0]
#define rs t[x][1]
#define tp(x) (t[f[x]][1]==x)
#define in(x) (t[f[x]][0]==x||tp(x))
void pp(int x){
    sl[x]=sl[ls]|sl[rs]|lc[x];
    mn[x]=min({mn[ls],mn[rs],lt[x]});
}
void add(int x,ll d){
    tg[x]+=d,mn[x]+=d,lt[x]+=d;
}
void adc(int x,int c){
    cl[x]=ctg[x]=c;
}
void pd(int x){
    if(tg[x]){
        if(ls)add(ls,tg[x]);
        if(rs)add(rs,tg[x]);
        tg[x]=0;
    }if(ctg[x]){
        adc(ls,ctg[x]),adc(rs,ctg[x]);
        ctg[x]=0;
    }
}
void ppd(int x){
    if(in(x))ppd(f[x]);pd(x);
}
void rot(int x){
    int y=f[x],k=tp(x),w=t[x][!k];
    t[f[w]=t[x][!k]=y][k]=w;
    if(in(y))t[f[y]][tp(y)]=x;
    f[x]=f[y],f[y]=x,pp(y);
}
void splay(int x){ppd(x);
    for(int y=f[x];in(x);rot(x),y=f[x])
        if(in(y))rot(tp(x)^tp(y)?x:y);pp(x);
}
void acs(int x){
    for(int y=0;x;x=f[y=x])
        splay(x),rs=y,pp(x);
}
int dfs(int x){
    sort(lk[x].begin(),lk[x].end());
    int nw=x,p;sm[x]=a[x],cl[x]=x;
    for(int y:lk[x]){
        p=++cnt;
        fa[L[p]=nw]=p;
        fa[R[p]=dfs(y)]=p;
        f[L[p]]=f[R[p]]=p;
        if(sm[L[p]]>=sm[R[p]]){
            d[p]=L[p];
            lc[R[p]]=1,cl[p]=cl[L[p]];
            lt[p]=sm[L[p]]-sm[R[p]];
        }else{
            d[p]=R[p];
            lc[L[p]]=1,cl[p]=cl[R[p]];
            lt[p]=sm[R[p]]-sm[L[p]];
        }
        sm[nw=p]=sm[L[p]]+sm[R[p]];
    }return mst[x]=nw;
}
vector<int>nd;
void rep(int x,int y){
    // cerr<<"rep:"<<x<<" "<<y<<endl;
    if(y!=d[x]){
        splay(d[x]),lc[d[x]]=1,pp(d[x]);
        splay(y),d[x]=y;
        int p=cl[y];
        splay(x),rs=0;
        lt[x]=-lt[x],pp(x);
        if(!lc[x])
            if(sl[ls]){
                for(x=ls;;){
                    pd(x);
                    if(sl[rs])x=rs;
                    else if(lc[x])break;
                    else x=ls;
                }
            }else{
                while(ls)pd(x),x=ls;
            }
        // cerr<<x<<" "<<p<<endl;
        splay(x),cl[x]=p,adc(rs,p);
        // cerr<<cl[x]<<endl;
        splay(y),lc[y]=0,pp(y);
    }
}
void access(int x){
    acs(x),splay(x);
    // cerr<<x<<" "<<sl[x]<<" "<<lc[x]<<endl;
    while(x&&sl[x]){
        while(1){
            pd(x);
            if(sl[rs])x=rs;
            else if(lc[x])break;
            else x=ls;
        }splay(x);
        nd.push_back(x);
        x=ls;
    }
    for(int p:nd)
        if(p!=rt)rep(fa[p],p);
    nd.clear();
}
void drop(int x){
    int mast=x;
    acs(x),splay(x),x=ls,splay(x);
    while(x&&mn[x]<=0){
        while(1){
            // cout<<"tg:"<<tg[x]<<endl;
            // cout<<"*"<<x<<" "<<ls<<" "<<rs<<" "<<mn[rs]<<" "<<mn[ls]<<" "<<lt[x]<<" "<<mn[x]<<endl;
            pd(x);
            // cout<<x<<" "<<ls<<" "<<rs<<" "<<mn[rs]<<" "<<mn[ls]<<" "<<lt[x]<<" "<<mn[x]<<endl;
            if(mn[rs]<=0)x=rs;
            else if(lt[x]<=0)break;
            else x=ls;
        }
        // cerr<<x<<endl;
        splay(x);
        // cerr<<x<<endl;
        nd.push_back(x);
        x=ls;
    }
    for(int p:nd)
        if(p!=mast){
            // cerr<<p<<" "<<d[p]<<" "<<lt[p]<<endl;
            if(d[p]==L[p]){
                // cerr<<p<<" "<<lt[p]<<endl;
                if(lt[p]<0)rep(p,R[p]);
            }else rep(p,L[p]);
        }
    nd.clear();
}
int main(){
    // freopen("copy.in","r",stdin);
    // freopen("copy.out","w",stdout);
    ios::sync_with_stdio(false);
    int i,j,k,l,r,x,y;
    cin>>n>>q,cnt=n;ll d;
    mn[0]=1e18;
    for(x=1;x<=n;++x)cin>>a[x];
    for(x=2;x<=n;++x){
        cin>>y;
        lk[y].push_back(x);
    }rt=dfs(1);
    for(x=1;x<=cnt;++x)pp(x);
    // for(x=n+1;x<=cnt;++x)
    //     splay(x),printf("x:%d d:%d L:%d R:%d lt:%lld\n",x,::d[x],L[x],R[x],lt[x]);
    // for(x=1;x<=cnt;++x)
    //     printf("x:%d lc:%d\n",x,lc[x]);
    while(q--){
        cin>>k>>x;
        if(k==1){
            splay(mst[x]);
            // cerr<<cl[mst[x]]<<endl;
            printf("%lld\n",a[cl[mst[x]]]);
            // if(x==3){
            //     splay(8),printf("%lld\n",lt[8]);
            // }
        }else{
            cin>>d,access(x),a[x]+=d;
            acs(x),splay(x);
            // for(int x=1;x<=cnt;++x)
            //     printf("x:%d ls:%d rs:%d f:%d\n",x,ls,rs,f[x]);
            // printf("x:%d mn:%lld\n",x,mn[x]);
            // printf("ls:%d mn:%lld\n",ls,mn[ls]);
            add(ls,d),pp(x);
            // if(!q)exit(0);
            // printf("x:%d mn:%lld\n",x,mn[x]);
            // cout<<"drop:"<<endl;
            drop(x);
            // cout<<"end:"<<endl;
        }
        // for(x=n+1;x<=cnt;++x)
        //     splay(x),printf("x:%d d:%d L:%d R:%d lt:%lld\n",x,::d[x],L[x],R[x],lt[x]);
        // fflush(stdout);
    }return 0;
}