【WC2020】有根树 题解

· · 题解

先丢出结论：每次修改 S 中的节点，答案的变化不超过 1，且可以从操作前的方案中进行 O(1) 次修改得到。

根据 w 的定义，可以发现对于 x,y\in S 且 x 是 y 的祖先，都满足 w_x\gt w_y。那么对于一条链上的点，我们肯定是选上面的那些点加入 C 中较优。从而可以得到，最终的最优解，取的必定是 w 最大的那些点。即 \min\limits_{x\in C}w_x\geq \max\limits_{x\not\in C} w_x。

令 X 表示一组解中 C 中的节点个数，Y 表示 \max\limits_{x\not\in C}w_x。

当 X>Y 的时候，我们不断尝试将 w_x>Y 的最小点从 C 中移除，来使得答案变小。

我们一定可以找到一组解，满足 X\geq Y。因为若 X\lt Y，则我们可以将 w_x=Y 且 x\not \in C 的一个节点加入 C 中。这个操作会使得 X 增加 1，而 Y 不会变大，因此能保证答案不会变劣。一直这么操作直到满足 X\geq Y 为止即可。

现在来说明开头的那个结论。考虑往 S 中添加一个节点 t 的情况。

因此，X 和 Y 均最多增加 1，所以答案最多增加 1。删除的情况同理可得。

然后只需要按照之前讲的方法调整答案到最优解即可。

现在的问题是，如何快速维护 \min\limits_{x\in C}w_x，\max\limits_{x\not\in C} w_x，以及它们对应的编号。

每加入一个节点 t 的时候，t 到根路径上的点的 w 值都会增加。因此一个简单的思路就是用树链剖分+线段树来维护 w 的值。

时间复杂度 O(m\log^2 n)，可以得到 80 分的好成绩。

似乎没有什么简单高效的方法维护所有的节点的信息。但是我们发现每次取用的都是最大/最小值，能否只维护部分节点的信息，并能做到较为高效的最值查询呢？

之前说过，对于 x,y\in S 且 x 是 y 的祖先，都满足 w_x\gt w_y，因此我们在树链剖分的时候，每条重链上只有 1 个节点可能成为最大值，只有 1 个节点可能成为最小值。那么在链加的时候，我们只需要考虑这些节点的答案变化情况就行了，而这样的节点只有 O(\log n) 个。因此可以直接记录这些点的 w，然后可以 O(1) 修改它的值。

我们还需要一个数据结构来维护这部分节点的最值。这个数据结构需要高效地实现插入/删除一个数，和查询最值，并且要较好地平衡 O(m\log n) 次插入/删除和 O(m) 次查询。

可以用 vEB 树做到 O(\log\log n) 插入 O(1) 查询，这样时间复杂度优化至 O(m\log n\log\log n)，但它非常不好写。

并且我们有更优的方案。

考虑以下维护办法：

我们可以这样理解这个算法：它在用暴力的方式找到 \min\limits_{x\in C}w_x 以及 \max\limits_{x\not\in C} w_x。而当插入/删除一个数已经无法使答案变优的时候（X=Y），它就会停下来。结合之前的分析，这样做的复杂度是正确的。

那么我们就不需要维护最值而是需要快速知道一个数有没有出现过以及快速提取这个数对应的编号。由于 w\leq n，所以用桶就可以记录出现情况。而插入/删除 x 以及提取，我们只需要开 n 个链表，插入/删除的时候在对应的链表上做就可以了。这些的复杂度都是 O(1) 的。

而对 S 的修改操作，会使得重链上的“可能成为最值”的点产生变化，这部分变化是 O(1) 的，因此对每条重链开 set 维护即可。在插入/删除 t 的时候，需要查询 w_t 的值，这个可以用树状数组实现。

最终我们的算法的时间复杂度为 O(m\log n) ，空间复杂度为 O(n)。

Code：

#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
const int N=5e5+5;
int n,m,head[N],cnt,sz[N],son[N],dep[N],fa[N],top[N],dfn[N],idx,idfn[N];
int X,Y;
int B[N];
bool inX[N];
inline void add(int i,int x){for(;i<=n;i+=i&-i)B[i]+=x;}
inline int ask(int i){int x=0;for(;i;i&=i-1)x+=B[i];return x;}
struct edge{
    int to,nxt;
}e[N<<1];
struct bucket{
    int pre[N],nxt[N],head[N];
    void _insert(int x,int v){
        int t=head[v];
        if(!t)head[v]=x,pre[x]=nxt[x]=0;else nxt[x]=t,pre[t]=x,head[v]=x,pre[x]=0;
    }
    void _erase(int x,int v){
        int t=head[v];
        if(x==t)head[v]=nxt[x],pre[nxt[x]]=0;else nxt[pre[x]]=nxt[x],pre[nxt[x]]=pre[x];
        pre[x]=nxt[x]=*pre=*nxt=0;
    }
    inline int get(int x){return head[x];}
}bc[2];//0:X  1:Y
struct Ldata{
    set<int>sX,sY;
    int _X,_Y;
    int wx,wy;
    void insertX(int x,int w){
        sX.insert(dfn[x]);
        if(!wx||wx>w){
            if(_X)bc[0]._erase(_X,wx);
            _X=x,wx=w;
            bc[0]._insert(_X,w);
        }
    }
    void insertY(int x,int w){
        sY.insert(dfn[x]);
        if(!wy||wy<w){
            if(_Y)bc[1]._erase(_Y,wy);
            _Y=x,wy=w;
            bc[1]._insert(_Y,w);
        }
    }
    void eraseX(int x,int w){
        sX.erase(dfn[x]);
        if(_X==x){
            bc[0]._erase(_X,wx);
            if(!sX.empty())_X=idfn[*sX.rbegin()],wx=ask(dfn[_X]+sz[_X]-1)-ask(dfn[_X]-1),bc[0]._insert(_X,wx);
            else _X=wx=0;
        }
    }
    void eraseY(int x,int w){
        sY.erase(dfn[x]);
        if(_Y==x){
            bc[1]._erase(_Y,wy);
            if(!sY.empty())_Y=idfn[*sY.begin()],wy=ask(dfn[_Y]+sz[_Y]-1)-ask(dfn[_Y]-1),bc[1]._insert(_Y,wy);
            else _Y=wy=0;
        }
    }
}dt[N];
void insert(int x){
    add(dfn[x],1);
    for(int v=x;v;v=fa[top[v]]){
        Ldata&nw=dt[top[v]];
        if(nw._X&&dfn[top[v]]<=dfn[nw._X]&&dfn[nw._X]<=dfn[v]){
            bc[0]._erase(nw._X,nw.wx);
            bc[0]._insert(nw._X,++nw.wx);
        }
        if(nw._Y&&dfn[top[v]]<=dfn[nw._Y]&&dfn[nw._Y]<=dfn[v]){
            bc[1]._erase(nw._Y,nw.wy);
            bc[1]._insert(nw._Y,++nw.wy);
        }
        if(nw.wy&&nw.wy>Y){
            const int id=nw._Y;
            const int w=nw.wy;
            nw.eraseY(id,w);
            nw.insertX(id,w);
            inX[id]=1;
            ++X;
        }
    }
    Ldata&nw=dt[top[x]];
    int w=ask(dfn[x]+sz[x]-1)-ask(dfn[x]-1);
    if(w>Y)nw.insertX(x,w),++X,inX[x]=1;else nw.insertY(x,w);
}
void erase(int x){
    Ldata&nw=dt[top[x]];
    int w=ask(dfn[x]+sz[x]-1)-ask(dfn[x]-1);
    if(inX[x])nw.eraseX(x,w),--X,inX[x]=0;else nw.eraseY(x,w);
    add(dfn[x],-1);
    for(int v=x;v;v=fa[top[v]]){
        Ldata&nw=dt[top[v]];
        if(nw._X&&dfn[top[v]]<=dfn[nw._X]&&dfn[nw._X]<=dfn[v]){
            bc[0]._erase(nw._X,nw.wx);
            bc[0]._insert(nw._X,--nw.wx);
        }
        if(nw._Y&&dfn[top[v]]<=dfn[nw._Y]&&dfn[nw._Y]<=dfn[v]){
            bc[1]._erase(nw._Y,nw.wy);
            bc[1]._insert(nw._Y,--nw.wy);
        }
        if(nw.wx&&nw.wx<Y){
            const int id=nw._X;
            const int w=nw.wx;
            nw.eraseX(id,w);
            nw.insertY(id,w);
            inX[id]=0;
            --X;
        }
    }
}
void dfs(int now){
    sz[now]=1,son[now]=0;
    for(int i=head[now];i;i=e[i].nxt)if(!dep[e[i].to]){
        dep[e[i].to]=dep[now]+1;
        fa[e[i].to]=now;
        dfs(e[i].to);
        sz[now]+=sz[e[i].to];
        if(!son[now]||sz[son[now]]<sz[e[i].to])son[now]=e[i].to;
    }
}
void dfs2(int now){
    idfn[dfn[now]=++idx]=now;
    if(son[now])top[son[now]]=top[now],dfs2(son[now]);
    for(int i=head[now];i;i=e[i].nxt)if(e[i].to!=son[now]&&dep[e[i].to]>dep[now])
    dfs2(top[e[i].to]=e[i].to);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        e[++cnt]=(edge){v,head[u]},head[u]=cnt;
        e[++cnt]=(edge){u,head[v]},head[v]=cnt;
    }
    dfs(dep[1]=1),dfs2(top[1]=1);
    X=0,Y=0;
    for(cin>>m;m--;){
        int op,v;
        cin>>op>>v;
        if(op==1)insert(v);else erase(v);
        while(X>Y){
            if(int id=bc[0].get(Y)){
                const int w=ask(dfn[id]+sz[id]-1)-ask(dfn[id]-1);
                dt[top[id]].eraseX(id,w);
                dt[top[id]].insertY(id,w);
                inX[id]=0;
                --X;
            }else++Y;
        }
        while(X<Y){
            if(int id=bc[1].get(Y)){
                const int w=ask(dfn[id]+sz[id]-1)-ask(dfn[id]-1);
                dt[top[id]].eraseY(id,w);
                dt[top[id]].insertX(id,w);
                inX[id]=1;
                ++X;
            }else--Y;
        }
        cout<<X<<'\n';
    }
    return 0;
}