P9592题解
这是一道经典绿题。所以为啥比赛主页显示黄？
比较具有挑战性，适合中国OIer水掉。
本题按照小编的函数由简到难进行讲解
这道题大制作法如下：
首先，对于主函数，我们可以来进行多组测试用例操作。
int main(){
long long T;
cin>>T;
while(T--){
_main();
}
}对于次主函数，即输出答案，我们可以作输入操作，不难发现根节点包含在
long long _main(){
long long n,d,k;
cin>>n>>d>>k;
er(n-1,d,k);
return 0;
} 接下来是重点，即寻找答案。
我们可以找最小深度，这里采用二分查找，并进行判断，最后输出。
void er(long long n,long long d,long long k){
if(k>n){//由于根节点不算叶节点，所以至少要分出k个节点
cout<<"NO"<<endl;
return;
}
if(n==0){//题目果然有骗人成分，输入的n为一就是无解，虽然这句话因为上头的那句话没有用，但这里特此提醒大家不要轻信题目
cout<<"NO"<<endl;
return;
}
if(n==d){//直接从根分叉
cout<<"YES"<<endl;
for(long long i=1;i<=n;i++){
cout<<"1 ";
}
cout<<endl;
return;
}
long long l,r;
l=2;
r=1000000;
r*=10000;//将r复制成10的10次方，由于害怕出问题，就这么干了
r+=9;//多点，以防万一
while(l<r){
long long mid;
mid=(l+r)/2;
if(dog(mid,n,d,k)){//dog函数会返回3种值：0,1,2，表示深度过低，深度合法，深度过高，时间复杂度O(1)
r=mid-dog(mid,n,d,k)+1;//由于dog函数不慢，所以干脆再算一遍，懒得多写了，本种情况为合法或过高
}else{
l=mid+1;//过低
}
}
if(dog(r,n,d,k)==1){//在判断一遍是否合法
cout<<"YES"<<endl;
pr(r,n,d,k);//输出，该函数类似dog函数
}else{
cout<<"NO"<<endl;//二分后都不合法，显然，无答案
}
}接下来就是疑点难点，判断函数，这个函数好像花了我一个半小时,思路就是先用最少的点搭到对应深度，即除了最后一层，每一层都选一个节点分支，
long long dog(long long s,long long n,long long d,long long k){
long long u,v,w;
u=s*k;//至少需要的总点数
if(u>n){//点不够用
return 2;//深度降低可能就好了
}
u=n-u;//计算剩的点
v=s*s+s;
v/=2;
v*=k;//由于每层都有k个点，计算深度直接用等差数列公式，计算k+2k+3k+4k...+sk,此处换成(1+2+3+4...+s)*k
if(v>d){//给的深度d不够
return 2;
}
v=d-v;//计算剩的深度
w=u*s;//假设剩的点都开得最大深度
if(w<v){//开成最大都不够填，肯定填不了
return 0;//深度应当提升，使得v变小
}
w-=v;//得到要在最大的基础上减去的深度
if(u>v){//即使每个点都是1，都显得多，导致装不下那么多深度，至于为什么放最后面，纯属脑子刚转过弯
return 2;
}
return 1;//剩下不难证明一定有办法使得成立，具体看下一个函数，pr。
}接下来是最难得函数，前半部分是由上面的函数复制粘贴的，不讲了，主要看后半部分，该函数是构造数的场所。
void pr(long long s,long long n,long long d,long long k){
long long u,v,w,f3;
f3=0;
u=s*k;
u=n-u;
v=s*s+s;
v/=2;
v*=k;
v=d-v;
w=u*s;
w-=v;//不用特判了，应为上面已经判了
//先构建到深度为s
for(long long i=0;i<s;i++){//深度-1
for(long long j=0;j<k;j++){//该层深度第j+1个点
cout<<i*k+1<<" ";//有上一深度的第一个点作父亲
++f3;//计算输出了几个点
}
}
long long f1,f2;
f1=w/(s-1);//每个剩的点从最大深度s到最小1深度减少s-1的深度，把能减的减了
f2=w%(s-1);//可能存在某点不用减到1
f2=s-f2;//计算剩的点的层数
f1=u-f1;//最大深度的数量，特别的，若最开始的余数f2不为0，就是最大深度数量+1（多了个f2）
if(f2!=s){//最开始不为0，即f2!=0,s-f2!=s-0
f1--;
}
while(f1--){//f1个
cout<<(s-1)*k+1<<" ";//深度为s的点查到s-1中第一个点
++f3;
}
if(f2!=s){//f2有存在就输出
cout<<(f2-1)*k+1<<" ";
++f3;
}
for(long long i=f3+1;i<=n;i++){//剩下的点深度为1，所以父亲为根
cout<<1<<" ";
}
cout<<endl;
}好吧，这道题我调了约两个半小时，别的题都没时间了，欢迎大家喷。