P6729 [WC2020] 有根树题解

树链剖分练习题。

显然。

所以 C 应尽量取最上面的点，则我们不需要考虑 C 的连通性。

• 一定有最优解使 \min\limits_{x \in C}w_x \ge |C| \ge \max\limits_{x \notin C}w_x。

因为当 |C| 增加时，\max\limits_{x \notin C}w_x 是在不断减小的。当 |C| < \max\limits_{x \notin C}w_x 时，此时增加 |C| 一定不会使答案变劣。

所以我们一直增加 |C| 直至满足上述条件即停止，此时的答案 |C| 一定是最优解，且此时一定有 \min\limits_{x \in C}w_x \ge |C|。^†

• 带修怎么做？

加入一个点时，它到根节点的路径上所有 \in S 的点的 w 都会增加 1，可能会使 \min\limits_{x \in C}w_x < \max\limits_{x \notin C}w_x，此时应把 C 中 w 最小的点替换成 C 以外 w 最大的点。

此外，它可能使 \max\limits_{x \notin C}w_x 增加，此时可能需要把它加入 C 中，答案增加 1。（为什么可以直接加？因为它的祖先的 w 肯定大于它本身的 w，所以祖先肯定都已经在 C 中了）

删除点同理，它可能使 \max\limits_{x \notin C}w_x 减少，此时可能可以丢掉 C 中 w 最小的点使答案减 1。

• 维护什么？

维护 \min\limits_{x \in C}w_x，\max\limits_{x \notin C}w_x 和它们的编号，以及 C 相关的东西。

• how？

树链剖分+线段树维护树上路径修改，线段树维护在 C 中 w 的最小值和为区间中在 S 且不在 C 中 w 的最大值即可，细节见代码。

复杂度 \mathcal O(q\log^2n) 虽然有点劣，但是能过。

• 代码

轻微压行，请见谅/kk

#define N 500005
int n,q,x,y,opt,t,now;//now 为目前的答案，即为 |C|
vector<int>v[N];
int fa[N],siz[N],son[N],cnt,dfn[N],top[N];
void dfs(int x,int f){//树剖预处理
    fa[x]=f,siz[x]=1;
    for(int i:v[x])if(i^f){
        dfs(i,x),siz[x]+=siz[i];
        if(siz[i]>siz[son[x]])son[x]=i;
    }
}
void dfs2(int x,bool flg){//树剖预处理
    dfn[x]=++cnt,top[x]=flg?top[fa[x]]:x;
    if(son[x])dfs2(son[x],1);
    for(int i:v[x])if(i^fa[x]&&i^son[x])dfs2(i,0);
}
struct segment{
    #define ls (x<<1)
    #define rs (x<<1|1)
    #define mid (l+r>>1)
    #define inf 0x3f3f3f3f
    int c[N<<2],s[N<<2],lazy[N<<2];
    /*
    c 为区间中在 C 中的 w 的最小值，s 为区间中在 S 且不在 C 中 w 的最大值，lazy 为区间加懒标记。
    如何区分是否在 C 中/在 S 中且不在 C 中？
    因为上面两个东西记录的都是最小/大值，所以对于不满足上面要求的点，我们在点上加/减 inf 即可。
    此时不满足要求的一定不会被记录到全局的最大/小值中。
    */
    void pushup(int x){c[x]=min(c[ls],c[rs]),s[x]=max(s[ls],s[rs]);}
    void pushdown(int x){
        if(lazy[x])
            c[ls]+=lazy[x],s[ls]+=lazy[x],c[rs]+=lazy[x],s[rs]+=lazy[x],
            lazy[ls]+=lazy[x],lazy[rs]+=lazy[x],lazy[x]=0;
    }
    void build(int x,int l,int r){//建树
        if(l==r)return c[x]=inf,s[x]=-inf,void();
        build(ls,l,mid),build(rs,mid+1,r),pushup(x);
    }
    void update(int x,int l,int r,int ql,int qr,int k){//区间加
        if(ql<=l&&r<=qr)return c[x]+=k,s[x]+=k,lazy[x]+=k,void();
        pushdown(x);
        if(ql<=mid)update(ls,l,mid,ql,qr,k);
        if(mid<qr)update(rs,mid+1,r,ql,qr,k);
        pushup(x);
    }
    //从 S 往 C 中增加一个点，此时增加的肯定是 C 以外 w 最大的点
    //目标：寻找这个点并修改
    void intoC(int x,int l,int r){
        if(l==r)return c[x]-=inf,s[x]-=inf,void();//丢进 C，扔出 S
        pushdown(x);
        if(s[ls]==s[x])intoC(ls,l,mid);//如果 C 以外 w 的最大值在左边则往左边走
        else intoC(rs,mid+1,r);//否则在右边
        pushup(x);
    }
    //从 C 中丢出一个点，此时丢出的肯定是 C 中 w 最小的点
    //目标：寻找这个点并修改
    void outoC(int x,int l,int r){
        if(l==r)return c[x]+=inf,s[x]+=inf,void();//扔出 C，丢进 S
        pushdown(x);
        if(c[ls]==c[x])outoC(ls,l,mid);//如果 C 中 w 的最小值在左边则往左边走
        else outoC(rs,mid+1,r);//否则在右边
        pushup(x);
    }
    //加入进 S/从 S 删除一个点 q
    void nodechg(int x,int l,int r,int q){
        if(l==r){
            if(c[x]<inf)c[x]+=inf,now--;//在 C 中，要删除，全局答案减少
            else if(s[x]<=0)s[x]+=inf;//两个都不在。要增加
            else s[x]-=inf;//在 S 且不在 C 中，要删除
            return;
        }
        pushdown(x);
        if(q<=mid)nodechg(ls,l,mid,q);
        else nodechg(rs,mid+1,r,q);
        pushup(x);
    }
}seg;
void work(int x,int y){//x 到根结点的路径增加 y
    while(x)
        seg.update(1,1,n,dfn[top[x]],dfn[x],y),x=fa[top[x]];
}
void solve(){
    cin>>n;
    fo(i,2,n)cin>>x>>y,v[x].push_back(y),v[y].push_back(x);
    dfs(1,0),dfs2(1,0),seg.build(1,1,n);
    cin>>q;
    while(q--){
        cin>>opt>>t;
        seg.nodechg(1,1,n,dfn[t]),work(t,opt==1?1:-1);
        if(seg.c[1]<seg.s[1])seg.outoC(1,1,n),seg.intoC(1,1,n);//替换点
        if(now<seg.s[1])seg.intoC(1,1,n),now++;//加点
        if(now>seg.c[1])seg.outoC(1,1,n),now--;//删点
        /*
        当需要删点时，删点后 s[1] 肯定是删点前的 c[1]，
        且需要满足 now-1>=删点后的 s[1]，即为 now>s[1]=c[1]
        */
        cout<<now<<'\n';
    }
}