CF1311E Construct the Binary Tree 做题记录

要求构造一个 $n$ 个节点的二叉树，节点 $1$ 为根，要使所有节点到根的距离之和为 $d$。要求先判断可不可以构造，如果可以输出 YES，下一行输出 $2$ 到 $n$ 号节点的父亲节点，否则输出 NO。

首先显然可以增量构造，每次把某个叶子接到同层的节点下，令深度总和增加 $1$。

那么设深度总和下界（构造一棵完全二叉树）为 $L$，深度总和上界（构造一条链）为 $R$，显然 $d<L$ 或者 $d>R$ 的情况下都是无解的。不妨猜测反之一定有解，尝试证明之，那么由于可以增量构造，所以只需要证明从完全二叉树开始，每次一定能把某个叶子接到同层的节点下。

显然每次操作深度尽量深的叶子是最优的，因为深度深的叶子被移走之后深度较浅的节点更容易暴露出来，成为新的可操作的叶子，并且接深度尽量深的叶子不会减少深度浅的叶子的数量。

那么由于每次都操作深度尽量深的叶子，所以一旦 $u$ 被操作了，并且下一次还能操作它，那么下一次操作一定还是操作它，所以 $u$ 的轨迹一定是这样的：

那么最后肯定能形成一条链，证毕。

代码如下：

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

const int S=5005;

int n,k;
bool vis[S];
int fat[S],du[S];
int dep[S];
int idx[S];

inline void slove()
{
	scanf("%d%d",&n,&k);
	int R=n*(n-1)/2;
	for(int i=1;i<=n;i++) vis[i]=false,du[i]=0;
	queue<int> q;
	q.push(1);
	vis[1]=true;
	dep[1]=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=1,cnt=0;i<=n&&cnt<2;i++)
		{
			if(!vis[i])
			{
				vis[i]=true;
				fat[i]=u;
				du[u]++;
				dep[i]=dep[u]+1;
				cnt++;
				q.push(i);
			}
		}
	}
	int L=0;
	for(int i=1;i<=n;i++) L+=dep[i];
	if(k<L||k>R) return void(puts("NO"));
	puts("YES");
	for(int tme=1;tme<=k-L;tme++)
	{
		for(int i=1;i<=n;i++) idx[i]=0;
		for(int i=1;i<=n;i++) if(du[i]<2&&(idx[dep[i]]==0||du[i]>0)) idx[dep[i]]=i;
		int u=0;
		for(int i=1;i<=n;i++) if(du[i]==0&&idx[dep[i]]!=0&&i!=idx[dep[i]]&&(u==0||dep[i]>dep[u])) u=i;
		du[fat[u]]--;
		du[fat[u]=idx[dep[u]]]++;
		dep[u]++;
	}
	for(int i=2;i<=n;i++) printf("%d ",fat[i]);
	printf("\n");
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T--) slove();
	return 0;
}