「Daily OI Round 1」Tree

题目描述

给定三个正整数参数 $n,d,k$,你需要构造出一棵根节点为 $1$ 的树,满足这棵树有 $n$ 个节点,每个节点到根节点的距离和为 $d$,除了叶节点以外每个节点的**直接**儿子数量**至少** $k$ 个,且所有节点的最大深度最小。 **注意事项:** - 距离:两个点之间的简单路径上的边的条数。 - 叶子节点:没有儿子的非根节点。 - 根节点深度为 $0$。

输入输出格式

输入格式


**本题有多组数据。** 第一行一个正整数 $T$,表示数据组数。 对于每组数据:共一行三个正整数 $n,d,k$,含义如题所示。

输出格式


对于每次询问,如果有解,第一行输出 `YES`,然后一行 $n-1$ 个正整数,第 $i$ 个正整数 $a_i$ 表示 $a_i$ 是 $i+1$ 的父亲节点,且 $a_i\leq i$;如果无解,输出 `NO`。 如果有多组合法的答案,可以任意输出其中一组。 **特别地,如果 $n=1$ 且有解,方案输出一行空行即可。**

输入输出样例

输入样例 #1

3
5 4 1
5 6 1
5 7 1

输出样例 #1

YES
1 1 1 1
YES
1 1 3 3
YES
1 2 2 2

输入样例 #2

3
5 4 2
5 6 2
5 7 2

输出样例 #2

YES
1 1 1 1
YES
1 1 3 3
NO

说明

### **样例解释** 对于第二组样例的第二组询问,$n=5,d=6,k=2$,即需要构造出含有 $5$ 个节点,各个节点到节点 $1$ 的距离和为 $6$ 且除叶节点外的节点至少有 $k$ 个儿子节点。 下面是样例构造的图: ![](https://cdn.luogu.com.cn/upload/image_hosting/wgir5yt5.png) 其中编号为 $1,2,3,4,5$ 的点到根节点 $1$ 的距离分别为 $0,1,1,2,2$,和为 $6$,满足条件。而且非叶子节点 $1,3$ 都含有至少 $2$ 个儿子节点,可以证明这是所有合法构造中节点的最大深度最小的解法,在此处为 $2$。 ### **数据范围** **本题开启捆绑测试。** |$\text{Subtask}$|分值|$n \le$|特殊性质| | :-----------: | :-------------:|:-----------: |:-----------: | |$0$|$5$|$10$|无| |$1$|$5$|$20$|无| |$2$|$5$|$10^5$|$k= n-1$| |$3$|$5$|$10^5$|$k= n-1$ 或 $n-2$| |$4$|$10$|$10^5$|$T=1$| |$5$|$70$|$10^5$|无| 对于全部数据,保证:$1 \le n \le 10^5$,$1 \le T \le 10^5$,$1 \le k \le 10^5$,$\sum n \le 10^6$,$1 \le d \le 10^{10}$。