CF1379E - Inverse Genealogy

题目大意

给定$n,k$，要求构造一棵二叉树满足

1.除了叶子以外的节点有两个儿子

2.称一个节点是特殊的：两个儿子中，一个儿子$size$至少是另一个的两倍

要求特殊的节点恰好有$k$个

分析

首先考虑一些简单的情况

1.$2|n$时不存在合法二叉树

2.$n$个节点的树，能够包含$0$个特殊节点当且仅当$\exists 2^i-1=n$

也就是能够构成一棵完美二叉树

3.除了$2$情况外的树，顺次放置每个节点得到的二叉树恰好包含1一个特殊点

那么当$k\leq 1$时的情况均可以被解决

否则，考虑通过加上一条极长的链来构造

即构造一个一边儿子大小为1，另一边顺次相接的链，这样能够做到最大利用点数

最多能得到$\frac{n-3} {2}$个特殊点

然而我们必须处理剩余点的分配，下面给出的构造能够解决$k\in [2,\frac{n-3} {2}]$的情况

通用构造

经过不断尝试得到的构造方法，好像很强

假设得到一条长度为$m$且右偏的上述链，将剩下的点分配到两个地方

1.根的左儿子

2.链底的右儿子

分配方式就是顺次放置每个节点得到的二叉树

设剩下节点个数+根的左儿+链底的右儿子$=c$

设$f(n)=1-[\exists 2^i-1=n]$，特别的，当$2|n$时，$f(n)=\infty$

假设根的左儿子分配大小为$x$，则新的树特殊点数目就是

$m-2+f(x)+f(c-x)+[c-x\ge 3]+[x\ge 2(n-1-x) \text{ or } (n-1-x)\ge 2x]$

枚举每一个$x\in[1,c-1]$，判定上式是否成立即可

const int N=1e5+10;

#define NO puts("NO"),exit(0)

int n,m;
int fa[N];

int chk(int a,int b) {
	if(a>b) swap(a,b);
	return a*2<=b;
}

void Out(){
	puts("YES");
	rep(i,1,n) printf("%d ",fa[i]);
	exit(0);
}

int Get(int l,int r) {
	rep(i,l+1,r) fa[i]=l-1+(i-l+1)/2;
	return l;
}

int Mincost(int x){
	if(~x&1) return 1e9;
	rep(i,0,17) if(x+1==(1<<i)) return 0;
	return 1;
}


int main(){
	n=rd(),m=rd();
	if(Mincost(n)==m) Get(1,n),Out();
	if(m==0) NO;
	if(~n&1) NO;
	if((m+1)*2>=n) NO;
	int r=(m+1)*2+1;
	if(r==n) {
		rep(i,1,m+1) fa[i*2]=i*2-1,fa[i*2+1]=i*2-1;
		Out();
	}

	r-=2;
	int c=n-r+2;
	if(m>1) rep(x,1,c-1) if(Mincost(x)+Mincost(c-x)-!chk(c-x,n-1-(c-x))+(x>=3)==1) {
		rep(i,1,m) fa[i*2]=i*2-1,fa[i*2+1]=i*2-1;
		int t=max(0,r-2);
		fa[Get(r-1,r+x-2)]=t;
		fa[2]=t;
		fa[Get(r+x-1,n)]=1;
		Out();
	}
	NO;
}