题解 CF772E【Verifying Kingdom】

· · 题解

获得更好的阅读体验（其实差不多）

题解

因为原树的所有非叶子节点都恰好有两个儿子，所以原树上 n 个叶子节点形成的虚树与原树同构。

考虑增量地构造虚树：假如前 (i-1) 个叶子的虚树已经求出来了，那么怎么找到第 i 个叶子的位置呢？

首先我们可以通过一次询问，确定叶子节点 i 相对于某个非叶子节点 u 的位置。具体地，设 x,y 分别为 u 的左、右子树内的两个叶子节点，那么可以通过询问 (x,y,i) 来确定 i 在 u 的左子树或右子树或与 u 没有祖先关系。

观察数据范围：询问次数不超过 10n 而 10=\lceil \log_2 1000\rceil。

于是想到点分治：对于每个叶子 i，都进行一次点分治。每次点分治对于当前连通块找到重心 rt（注意这个重心不能是叶子节点，若分治到一个只有单一叶子节点的连通块，新建点作为这个连通块和 i 的父亲即可），并询问 rt 与 i 的位置关系。设与 rt 相邻的、朝向 i 的那个点（这个点有可能是 rt 的儿子，也有可能是 rt 的父亲）为 v，基于这个位置关系，有如下几种可能：

另外，注意到前两个叶子节点是不需要点分治确定位置的，因为它们在虚树上一定有共同的父亲。

因为每次点分治都只会分治到某个子树，而新一轮分治的连通块大小会减半，因此时间复杂度为 \mathcal{O}(n(n+\frac{n}{2}+\frac{n}{4}+\dots))=\mathcal{O}(n^2)，询问次数为 \mathcal{O}(n\log n)。

代码

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <cassert>
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
template<typename T> void Read(T &x){
    x=0;int _f=1;
    char ch=getchar();
    while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    x=x*_f;
}
template<typename T,typename... Args> void Read(T &x,Args& ...others){
    Read(x);Read(others...);
}
typedef long long ll;
const int N=2005;
int n,tot,e[N][3],sym[N][2],root;
//e[u][0] 表示 u 的父亲，e[u][1,2] 分别表示 u 的左右儿子
//sym[u][0,1] 分别表示以 u 的左、右儿子为根的子树内的任一叶子节点
void Link(int u,int x,int v){
    e[u][x]=v,e[v][0]=u;
}
int vis[N],siz[N],mxsiz[N];
int GetSize(int u,int pre){
    int res=1;
    For(i,0,2){
        if(!e[u][i]||e[u][i]==pre||vis[e[u][i]]) continue;
        res+=GetSize(e[u][i],u);
    }
    return res;
}
int rt;
void GetRoot(int u,int pre,int tsiz){
    siz[u]=1,mxsiz[u]=0;
    For(i,0,2){
        if(!e[u][i]||e[u][i]==pre||vis[e[u][i]]) continue;
        GetRoot(e[u][i],u,tsiz);
        mxsiz[u]=max(mxsiz[u],siz[e[u][i]]);
        siz[u]+=siz[e[u][i]];
    }
    mxsiz[u]=max(mxsiz[u],tsiz-siz[u]);
    if(e[u][1]&&mxsiz[u]<=tsiz/2) rt=u;
}
void Decomp(int u,int lf){//点分治。lf:需要确定位置的叶子节点
    if(!e[u][1]){//特判分治到叶子的情况
        int f=e[u][0],sn;
        if(e[f][1]==u) sn=1;
        else sn=2;
        Link(f,sn,++tot);Link(tot,1,u);Link(tot,2,lf);
        sym[tot][0]=u,sym[tot][1]=lf;
        return;
    }
    rt=0;
    int s=GetSize(u,0);
    GetRoot(u,0,s);
    u=rt;
    vis[u]=1;
    printf("%d %d %d\n",sym[u][0],sym[u][1],lf);
    fflush(stdout);
    int nxt;char temp[10];
    scanf("%s",temp);
    if(temp[0]=='X') nxt=0;
    else if(temp[0]=='Y') nxt=2;
    else nxt=1;
    if(e[u][nxt]&&!vis[e[u][nxt]]){
        Decomp(e[u][nxt],lf);
    }else{
        int v=e[u][nxt];
        if(nxt==0){//往上走
            if(!v){
                Link(++tot,1,u);Link(tot,2,lf);
                sym[tot][0]=sym[u][0],sym[tot][1]=lf;
                root=tot;return;
            }
            int sn=e[v][1]==u?1:2;
            Link(v,sn,++tot);Link(tot,1,u);Link(tot,2,lf);
            sym[tot][0]=sym[u][0],sym[tot][1]=lf;
        }else{//往左/右儿子走
            Link(u,nxt,++tot);Link(tot,1,v);Link(tot,2,lf);
            if(!e[v][1]) sym[tot][0]=v;
            else sym[tot][0]=sym[v][0];
            sym[tot][1]=lf;
        }
    }
}
int main(){
    scanf("%d",&n);
    root=tot=n+1;
    Link(root,1,1);Link(root,2,2);
    sym[n+1][0]=1,sym[n+1][1]=2;
    For(i,3,n){
        memset(vis,0,sizeof vis);
        Decomp(root,i);
    }
    puts("-1");
    For(i,1,tot) printf("%d ",e[i][0]?e[i][0]:-1);
    return 0;
}