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\)，基于这个位置关系，有如下几种可能：

• \(v\) 之前没有作为分治中心过：递归到 \(v\) 进行点分治即可。

• \(i\) 不在 \(rt\) 的子树内（即需要往上走）：

  • \(rt\) 是虚树的根：我们需要在 \(rt\) 上面新加一个点，作为新的根，并令 \(rt,i\) 为新点的左右儿子。
  • 否则，此时我们已经知道了 \(v\) 曾经作为分治中心，并且它一定是上一轮点分治的分治中心。也就是说，\(i,rt\) 在 \(v\) 的同一子树内，且 \(i\) 不在 \(rt\) 的子树内。这显然是不可能的，因此我们要新建一个点，其左右儿子分别为 \(rt,i\) 而父亲为 \(v\)。

• \(i\) 在 \(rt\) 的子树内，而 \(v\) 之前被访问过：同上新建点即可。

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

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

代码

#include 
#include 
#include 
#include 
#include 
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 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 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;
}