题解：P10214 [CTS2024] 投票游戏

gcx114514 · 2024-11-21 19:31:11 · 题解

很有意思的黑题，每一步都很自然。

思路

首先考虑如何比较两个点的删除时间，发现可以通过比较两个点删除时的票数来进行比较我们设 dp_i 表示点 i 被删除时的票数，

那么如果 dp_x>dp_y 或者 dp_x=dp_y 且 x>y 那么 x 比 y 先删除。

注意到这是一个树形结构，每个人只会影响其祖先的票数，每个人的初始票数为 a_x+\sum\limits_{v\in son(i)} b_v，但是如果 dp_v>dp_i 说明 v 比 i 先删除，那么 dp_i\gets dp_i-b_v，可以将儿子按照 dp 值排序，令 sum_{u,i} 表示 u 排序完成的儿子的 b 的前缀和，那么我们需要找到 a_u+\sum b_v-sum_{u,i-1}<dp_{son_{u,i}} 即 a_u+\sum b_i <sum_{u,i-1}+dp_{son_{u,i}}，因为有修改，考虑用平衡树来维护，可以在上面二分得到答案，即维护前缀 {sum_{u,i-1}+dp_{son_{u,i}}} 的最小值，这样有了 O(n\log n+qd\log n) （其中 d 表示树的深度）的做法。

考虑优化，每次修改是影响点 u 到根这一条路径，考虑能否进行重剖进行优化。一个常用技巧：考虑对每个点只去维护其轻儿子的平衡树，考虑每次加入重儿子的贡献，在换链时作特殊处理。假设对于对于在轻儿子的平衡树上达到的答案是 val，如果 val>dp_{son_u} 时可以知道 u 一定在 son_u 删除之前删除。否则应该用 a_u+\sum b_v -b_{son_u} 到平衡树上二分得到答案。注意到这与每次更新与 dp_{son_u} 没有关系，这是分段函数，可以用线段树维护，因为我们并没有考虑重儿子的情况，所以查询时要查询从我这开始到重链底部的贡献。现在的复杂度是 O(n\log n+q\log^2 n) 的。

::::info[code]

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb emplace_back
#define mid ((l+r)>>1)
#define int long long
#define mk make_pair
#define rs now<<1|1
#define ls now<<1
#define reaD read
#define raed read
#define haed head
#define cotu cout
#define se second
#define fi first
#define itn int
using namespace std;
bool Mst;
const int Max=2e5+10;
const int mod=998244353;
const int inf=1e18+10;

inline int read(){
    int res=0,v=1;
    char c=getchar();
    while(c<'0'||c>'9'){v=(c=='-'?-1:1);c=getchar();}
    while(c>='0'&&c<='9'){res=(res<<3)+(res<<1)+(c^48);c=getchar();}
    return res*v;
}

int b[Max],dp[Max],sumb[Max];
int root[Max],Val[Max],n;

struct tree{
    int minn,sum,ch[2],key;
    #define ch(x,i) tr[x].ch[i] 
    #define minn(x) tr[x].minn
    #define sum(x) tr[x].sum
    #define key(x) tr[x].key
}tr[Max];

struct FHQ{  //平衡树编号与树的编号对应，方便处理 

    void pushup(int now){
        sum(now)=sum(ch(now,0))+b[now]+sum(ch(now,1));
        minn(now)=min(minn(ch(now,0)),min(sum(ch(now,0))+dp[now],sum(ch(now,0))+b[now]+minn(ch(now,1)))); 
    } 

    void Split(int now,pii val,int &x,int &y){
        if(!now){x=y=0;return;}
        if(dp[now]>val.fi||(dp[now]==val.fi&&now>val.se)){
            x=now;
            Split(ch(now,1),val,ch(x,1),y);
        }else{
            y=now;
            Split(ch(now,0),val,x,ch(y,0));
        }
        pushup(now);
    } 

    int merge(int x,int y){
        if(!x||!y)return x|y;
        if(key(x)>key(y)){
            ch(x,1)=merge(ch(x,1),y);
            pushup(x);return x;
        }else{
            ch(y,0)=merge(x,ch(y,0));
            pushup(y);return y;
        }
    }

    int Query(int now,int val){
        if(!now)return val;
        if(minn(ch(now,0))<val)return Query(ch(now,0),val);
        else if(sum(ch(now,0))+dp[now]<val)return val-sum(ch(now,0));
        else return Query(ch(now,1),val-sum(ch(now,0))-b[now]);
    }
    void insert(int x,int y){
        int xx,yy;
        Split(root[x],mk(dp[y],y),xx,yy);
        minn(y)=dp[y],sum(y)=b[y];key(y)=rand();
        root[x]=merge(xx,merge(y,yy)); 
    }

    void Del(int x,int y){
        int xx,yy,zz;
        Split(root[x],mk(dp[y],y),xx,yy);
        Split(yy,mk(dp[y],y-1),yy,zz);root[x]=merge(xx,zz);
    }

}t1;

struct Sg{
    int lim,x,y;//小于lim返回x,否则返回y
    Sg(int lim=0,int x=0,int y=0):
        lim(lim),x(x),y(y){;}
    int chk(int z){return z<lim?x:y;}

    Sg operator +(Sg b){return Sg(lim,b.chk(x),b.chk(y));}
}f[Max];  //每个点的函数 

struct SGT{  //线段树维护分段函数。 

    Sg tr[Max<<2];

    void pushup(int now){
        tr[now]=tr[now<<1|1]+tr[now<<1];
    }

    void Modify(int now,int l,int r,int to,Sg val){
        if(l==r){tr[now]=val;return;}
        if(to<=mid)Modify(ls,l,mid,to,val);
        else Modify(rs,mid+1,r,to,val);
        pushup(now);
    }

    Sg Query(int now,int l,int r,int L,int R){
        if(L<=l&&R>=r)return tr[now];
        if(R<=mid)return Query(ls,l,mid,L,R);
        if(L>mid)return Query(rs,mid+1,r,L,R);
        return Query(rs,mid+1,r,L,R)+Query(ls,l,mid,L,R);
    }
}t2;

struct Node{
    int to,next;
    Node(int to=0,int next=0):
        to(to),next(next){;}
}a[Max<<1];
int head[Max],cnt;
void add(int x,int y){
    a[++cnt]=Node(y,head[x]);
    head[x]=cnt;
}

struct Tree{
    int siz,son,dep,fa,id,end,top;
    #define siz(x) bbb[x].siz
    #define top(x) bbb[x].top
    #define son(x) bbb[x].son
    #define dep(x) bbb[x].dep
    #define end(x) bbb[x].end
    #define id(x) bbb[x].id
    #define fa(x) bbb[x].fa 
}bbb[Max];

Sg Queryf(int now){
    if(!son(now))return Sg(0,0,Val[now]);
    int val=t1.Query(root[now],Val[now]+sumb[now]); //轻儿子的值。 
    return Sg(val,val,t1.Query(root[now],Val[now]+sumb[now]-b[son(now)]));
} 

void dfs1(int now,int fa){
    siz(now)=1;fa(now)=fa;dep(now)=dep(fa)+1;
    for(int i=head[now];i;i=a[i].next){
        int to=a[i].to;
        if(to==fa)continue;
        sumb[now]+=b[to];
        dfs1(to,now);siz(now)+=siz(to);
        son(now)=siz(son(now))>siz(to)?son(now):to;
    } 

    for(int i=head[now];i;i=a[i].next){
        int to=a[i].to;
        if(to==fa||to==son(now))continue;
        t1.insert(now,to); 
    }
    f[now]=Queryf(now);dp[now]=f[now].chk(dp[son(now)]); 
} 

int Res=0;

void dfs2(int now,int top){
    id(now)=++Res;top(now)=top;t2.Modify(1,1,n,id(now),f[now]); 
    if(son(now)){
        dfs2(son(now),top);end(now)=end(son(now));
    }else end(now)=now;   //记录链底 
    for(int i=head[now];i;i=a[i].next){
        int to=a[i].to;
        if(!id(to))dfs2(to,to);
    } 
}

void work(int x,int opt=-1){
    t1.Del(fa(x),x);
    if(opt!=-1)b[x]=opt;
    dp[x]=t2.Query(1,1,n,id(x),id(end(x))).chk(0);
    t1.insert(fa(x),x);
}

void Modify(int x){
    while(x){
        f[x]=Queryf(x);t2.Modify(1,1,n,id(x),f[x]);
        x=top(x);
        if(x!=1){work(x);}
        else return ;
        x=fa(x);
    }
}

bool Med;
signed main(){n=read();
    n=read();int q=read();
    for(int i=2;i<=n;++i)add(read(),i);
    for(int i=1;i<=n;++i)Val[i]=read();
    for(int i=1;i<=n;++i)b[i]=read(); 
    minn(0)=inf;
    dfs1(1,0);
    dfs2(1,1);
    for(int i=1;i<=q;++i){
        int opt=read();
        if(opt==1){
            int p,x,y;
            p=read(),x=read(),y=read();
            Val[p]=x;Modify(p);
            if(p!=1){
                sumb[fa(p)]-=b[p];sumb[fa(p)]+=y;
                if(p!=son(fa(p)))work(p,y);
                b[p]=y;
                Modify(fa(p));
            }
        }else{
            int x,y;
            x=read(),y=read();
            int tag=x>y; 
            x=t2.Query(1,1,n,id(x),id(end(x))).chk(0);
            y=t2.Query(1,1,n,id(y),id(end(y))).chk(0);
            if(x>y||((x==y)&&(tag)))cout << 0 << "\n";
            else cout << 1 << "\n";
        }
    }
    cerr<< "Time: "<<clock()/1000.0 << "s\n";
    cerr<< "Memory: " << (&Med-&Mst)/1000000.0 << "MB\n";
    return 0;
}

::::