[✗✓OI R1] T6 天动万象

· · 题解

自己的赛时做法和官方做法略有不同，就来发一下。

这题操作一次后，子树中的叶子节点会变成 0，考虑复杂度均摊，每次操作复杂度与 删去叶子个数 相关，复杂度就正确。

观察到每次向上操作的时候，如果是一条链就相当于链上所有下面的权值向上移动，只有儿子个数 \ge 2 的时候才是把儿子加起来。

考虑一开始把“链”全部缩起来，相当于建叶子节点的虚树，这样保留的“链”条数就是 O(\text{叶子节点个数})。

对于每条链（虚树上的一条边），开一个 FHQ-Treap 维护链上的权值。

修改操作：直接 dfs 虚树的那个子树，对于下面每条链都是删掉最上面一个权值，在最下面加入每个儿子边的权值和。其实就是在模拟操作，都可以用平衡树实现。

查询操作：对于查询点所在的那条链，可以 split 出下面一段；另外在子树里的权值可以 dfs 序线段树，在前面修改操作的时候就维护好。

然后你写了，交了，只能拿 28 分！（链，菊花，随机树）

上面那个做法是有复杂度问题的，在一些叶子节点被删掉之后，可能出现了更多儿子个数 = 1 的点，那就要继续缩起来，才能保证复杂度。

想了一会，发现可以用并查集维护每个点的链顶，每次修改每个点的一个儿子的平衡树如果被删空那就把这个儿子从它的儿子列表里删掉，如果只剩一个儿子了就要把儿子链缩到它自己链上，相当于两个 treap 合并一下。（有很多细节）

（注意每次修改完平衡树都要在 dfn 线段树里 update 一下）

代码不长，才 200 行，下面是删去部分的代码：

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 1000005
#define inf 0x3f3f3f3f

int n,m,a[maxn],fa[maxn];
vi e[maxn],dw[maxn];

int ftop[maxn],dep[maxn];
int dfn[maxn],out[maxn],idx;

inline int top(int u){
    while(u!=ftop[u])u=ftop[u]=ftop[ftop[u]];
    return u;
}

struct sgt{
    ll val[maxn<<2];
    void mdf(int p,int l,int r,int x,ll v){
        if(l==r)return val[p]=v,void();
        int mid=l+r>>1;
        x<=mid?mdf(p<<1,l,mid,x,v):mdf(p<<1|1,mid+1,r,x,v);
        val[p]=max(val[p<<1],val[p<<1|1]);
    }
    ll ask(int p,int l,int r,int ql,int qr){
        if(ql>qr)return 0;
        if(l>=ql&&r<=qr)return val[p];
        int mid=l+r>>1;ll res=0;
        if(ql<=mid)res=max(res,ask(p<<1,l,mid,ql,qr));
        if(qr>mid)res=max(res,ask(p<<1|1,mid+1,r,ql,qr));
        return res;
    }
}T;

int rt[maxn];
ll val[maxn],mx[maxn];
int ls[maxn],rs[maxn],cnt,sz[maxn];
unsigned int rnd[maxn];
mt19937 qwqwq(1337); 
inline int newn(int x){
    int u=++cnt;
    val[u]=mx[u]=x;
    sz[u]=1;
    return u;
}
inline void up(int p){
    mx[p]=max(mx[ls[p]],max(mx[rs[p]],val[p]));
    sz[p]=sz[ls[p]]+sz[rs[p]]+1;
}
int merge(int u,int v){
    if(!u||!v)return u|v;
    if(rnd[u]<rnd[v])return rs[u]=merge(rs[u],v),up(u),u;
    return ls[v]=merge(u,ls[v]),up(v),v;
}
void split(int p,int k,int&x,int&y){
    if(!p)return x=y=0,void();
    if(sz[ls[p]]<k) x=p,split(rs[p],k-sz[ls[p]]-1,rs[x],y),up(x);
    else y=p,split(ls[p],k,x,ls[y]),up(y);
}
inline void upd(int u){
    T.mdf(1,1,n,dfn[u],mx[rt[u]]);
}

void dfs(int u,int tp)
{
    ftop[u]=tp;
    dep[u]=dep[fa[u]]+1;
    dfn[u]=++idx;
    rt[tp]=merge(rt[tp],newn(a[u]));
    if(e[u].size()>=2){
        for(auto v:e[u])
            dw[tp].pb(v),dfs(v,v);
    }
    else if(e[u].size()==1) dfs(e[u][0],tp);
    if(u==tp) upd(u);
    out[u]=idx;
}

inline ll ask(int u)
{
    int t=top(u);
    int szl=dep[u]-dep[t],x,y;
    split(rt[t],szl,x,y);
    ll res=mx[y];
    res=max(res,T.ask(1,1,n,dfn[u]+1,out[u]));
    rt[t]=merge(x,y);
    return res;
}

void suo(int u)
{
    int v=dw[u][0];
    ftop[v]=top(u);
    rt[u]=merge(rt[u],rt[v]);
    rt[v]=0;
    swap(dw[u],dw[v]),dw[v].clear();
    upd(v),upd(u);
}

vi del;
ll work(int u)
{
    int x,y;
    split(rt[u],1,x,y);
    ll ret=val[x];
    val[x]=0;
    if(!dw[u].size()){
        rt[u]=y;
        return upd(u),ret;
    }
    vi o;
    for(auto v:dw[u]){
        ll w=work(v);
        if(mx[rt[v]]) o.pb(v);
        val[x]+=w;
    }
    mx[x]=val[x];
    dw[u]=o;
    rt[u]=merge(y,x);
    if(dw[u].size()==1) del.pb(u);
    return upd(u),ret;
}
void shift(int u)
{
    int x,y,z,szl=dep[u]-dep[top(u)];
    split(rt[top(u)],szl,x,y);
    split(y,1,y,z);
    del.clear();

    int t=top(u);
    val[y]=0;
    vi o;
    for(auto v:dw[t]){
        ll w=work(v);
        val[y]+=w;
        if(mx[rt[v]]) o.pb(v);
    }
    mx[y]=val[y];
    dw[t]=o;
    if(dw[t].size()==1) del.pb(t);
    rt[t]=merge(merge(x,z),y);
    upd(t);

    for(auto x:del) suo(x);
}

signed main()
{
//  freopen("my.out","w",stdout);
    n=read(),m=read();
    For(i,1,n)a[i]=read(),rnd[i]=qwqwq();
    For(i,2,n)fa[i]=read(),e[fa[i]].pb(i);
    dfs(1,1);
    For(_,1,m){
        int op=read(),x=read();
        if(op==2)shift(x);
        else printf("%lld\n",ask(x));
    }
    return 0;
}