自动搬运

查看原文

来自洛谷，原作者为

	Acoipp We shall never surrender!

搬运于2025-08-24 22:49:55，当前版本为作者最后更新于2023-08-14 19:57:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

下面是出题人题解：

因为是到根节点的距离，所以设根节点深度为 $0$，其余节点同理，题意转化为了所有节点深度和为 $d$。

subtask0

暴力可做，枚举每个点的父亲节点，时间复杂度 $O(n!)$。

subtask1

节点数量为 $n$ 的树的节点的深度之和的种类很少，所以对于每一种深度搜索一下再剪个枝就可以了。

subtask2

很显然，构造菊花图，然后判断深度之和是否等于 $d$ 即可。

subtask3

还是构造菊花图，但是当 $n$ 很小的时候也可以构造出非菊花图的解，特判一下就可以了。

subtask4

给随机数算法的分。

subtask5

很显然，对于深度相同的节点，把它们的儿子都移到这个深度的某个节点下面是可行的，那么这时题目变成了每一层至少 $k$ 个节点，除开第一层。

题目还要求最大深度最小，枚举最大深度，然后每个深度（除了根节点所在深度）都先安排 $k$ 个点上去，剩下的点就随便选择一个小于等于当前枚举的深度安排就可以了。

如果剩下 $i$ 个点，当前枚举深度为 $x$，每层安排 $k$ 个点后深度之和 $d$ 减去这些点的深度后为 $y$。

那么有解当且仅当 $i \le y \le i \times x$，然后构造就很简单了。

确定每个点的深度，然后深度 $x$ 的所有点的父亲设为深度 $x-1$ 的某个节点即可。

深度最大为 $n$，时间复杂度不计算排序的话是 $O(\sum n)$。

#include<bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
ll t,k,n,d,i,j,l,p,o,temp,dep[N],tot,ans[N];
int main(){
	ios::sync_with_stdio(false);
	cin>>t;
	while(t--){
		tot=0;
		cin>>n>>d>>k;
		if(n==1){
			if(d==0){
				cout<<"YES\n";
				continue;
			}
			else{
				cout<<"NO\n";
				continue;
			}
		}
		temp=0;
		for(i=1;i<=n;i++){
			if(i*(i+1)/2*k>d||i*k+1>n) break;
			j = d-i*(i+1)/2*k;
			l = (n-i*k-1);
			if(l*i>=j&&l<=j){
				j=i*l-j;
				temp=1;
				cout<<"YES\n";
				for(p=1;p<=i;p++){
					for(o=1;o<=k;o++) dep[++tot]=p;
				}
				for(p=1;p<=l;p++) dep[++tot]=i;
				for(p=tot-l+1;p<=tot;p++){
					if(dep[p]-1>=j){
						dep[p]-=j;
						break;
					}
					else j-=(dep[p]-1),dep[p]=1;
				}
				sort(dep+1,dep+tot+1);
				ans[0] = 1;
				for(p=1;p<=tot;p++) cout<<ans[dep[p]-1]<<" ",ans[dep[p]]=p+1;
				cout<<endl;
				break;
			}
		}
		if(!temp) cout<<"NO\n";
	}
	return 0;
}