CF1990E2. Catch the Mole(Hard Version)题解

· · 题解

Link

感觉我的做法比较奇怪，但感觉很对。

发现 N 比较小，考虑暴力一点的做法。

考虑如何查找所需次数最少，经典想法就是子树大小接近 \frac{num}{2} ，num 是现在还存在的树的大小（每一次若不存在于子树内则砍掉子树再加回来每一个剩余点的父亲，再砍掉所有叶子，若存在则砍掉除子树之外的部分）。

然后暴力维护这一棵树，如果用 set 来维护则复杂度是单次查询 O(n\log n) 。

为什么这样能较优？考虑极端情况——菊花图，这样的情况下，子树大小是距离 \frac{num}{2} 相当远的。

但是注意到每一次若不在子树中则会向上走一格。而菊花图叶子非常多。这种策略在菊花图时能跑的非常快。

那么在链的情况下呢？容易发现若是链，则 \frac{num}{2} 是非常容易接近的一个数。所以其也能跑的非常快。

我估计一个上界是 O(\sqrt n) 级别的，若有读者能够提出证明欢迎发在评论区。

实现方法则是用 set 维护一个点集，表示这些点可能会存在 mole 。按照dfn排序后倒序处理子树和，类似dp。

然后找到子树和最接近 \frac{num}{2} 且最小的点，对其查询。

若 mole 在其子树内则遍历点集，删掉子树外的点。若不在则删掉子树内的点，再将子树外的点删掉，其父亲加入。

容易发现每一种操作可能涉及的点数量都是 O(n) 。这样单次询问即为 O(n\log n) 。

容易发现删掉子树内/外所有点相当于dfn序列上的一个区间覆盖，可以使用差分预处理，但将父亲插入较难实现。可以找出一个点距离其子树内叶子最远距离，然后考虑一次整体上移造成的影响：删掉所有叶子，加入根的父亲（若有）。删叶子可以通过刚刚所说的预处理子树内距叶子最远距离来实现，加入父亲只会造成 O(1) 级别的影响。这样可以把复杂度优化到 O(n) 。

但是单 \log 的方法在 test 2 ILE 了，线性没调出来，后来写了个 vector 暴力删 过了。有点太逆天了。

其原理与用 set 维护一样，同样是删除与去重。但是由于 vector 删除复杂度高且去重也要手动所以不优。

以下是 O(n^2) 的 vector 暴力删做法代码。

code

const int N=5e3+5;

struct edge{
    int v,nxt;
}e[N<<1];
int head[N],tott;
void add(int u,int v){e[++tott]={v,head[u]},head[u]=tott;}

vector<int> vec;

int dep[N],dfn[N],cnt;
int L[N],R[N];
int fa[N];
void dfs(int u,int faa){
    L[u]=dfn[u]=++cnt;
    dep[u]=dep[faa]+1;
    fa[u]=faa;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(v==faa)
            continue;
        dfs(v,u);
    }R[u]=cnt;
}

bool cmp(int x,int y){
    return dep[x]==dep[y]?dfn[x]<dfn[y]:dep[x]<dep[y];
}

bool tag[N];
int sum[N];
bool ask(){
    int id=vec.back();
    int num=vec.size()/2;
    for(int i=vec.size()-1;i>=0;i--){
        int v=vec[i];
        sum[v]++;
        if(abs(sum[v]-num)<abs(sum[id]-num)||
          (abs(sum[v]-num)==abs(sum[id]-num)&&sum[v]<sum[id]))
            id=v;
        if(tag[fa[v]])
            sum[fa[v]]+=sum[v];
    }
    for(int i:vec)
        sum[i]=0;//清空
    cout<<"? "<<id<<endl;
    int opt=read();
    if(opt){
        for(int i=0;i<vec.size();i++){
            int v=vec[i];
            if(dfn[v]>R[id]||dfn[v]<L[id]){
                tag[v]=0;
                vec.erase(vec.begin()+i);
                i--;
            }
        }
    }else{
        for(int i=0;i<vec.size();i++){
            int v=vec[i];
            if(dfn[v]<=R[id]&&dfn[v]>=L[id]){
                tag[v]=0;
                vec.erase(vec.begin()+i);
                i--;
            }else if(v!=1){
                tag[v]=0;
                tag[fa[v]]=1;
                vec[i]=fa[v];
                if(i>0&&vec[i]==vec[i-1]){//去重，在按照深度及dfn序排序后，若同时将数列中每一个点替换为其父亲，则相同的数字一定出现在连续的一段
                    vec.erase(vec.begin()+i);
                    i--;
                }
            }
        }
    }
    if(vec.size()==1){
        cout<<"! "<<vec[0]<<endl;
        vector<int> tmp;
        swap(tmp,vec);//清空vector
        return 1;
    }return 0;
}

signed main(){
    signed _T=read();
    while(_T--){
        int n=read();
        for(int i=1;i<n;i++){
            int u=read(),v=read();
            add(u,v),add(v,u);
        }
        dfs(1,0);//预处理
        for(int i=1;i<=n;i++)
            vec.pb(i),tag[i]=1;//tag表示还存在于点集内
        sort(all(vec),cmp);
        while(!ask());
        for(int i=1;i<=n;i++)
            head[i]=tag[i]=0;
        tott=0;
        cnt=0;
    }
    return 0;
}