P9592 "Daily OI Round 1" Tree

Given three positive integers $n, d, k$, you need to construct a rooted tree with root node $1$ such that: - The tree has $n$ nodes. - The sum of distances from every node to the root is $d$. - For every node that is not a leaf, the number of its **direct** children is **at least** $k$. - Among all valid trees, the maximum depth of all nodes is as small as possible. **Notes:** - Distance: the number of edges on the simple path between two nodes. - Leaf node: a non-root node that has no children. - The depth of the root is $0$.

**This problem contains multiple test cases.** The first line contains a positive integer $T$, the number of test cases. For each test case, there is one line with three positive integers $n, d, k$, with the meaning as described above.

For each test case: - If a solution exists, output `YES` on the first line, then output $n-1$ positive integers on the next line. The $i$-th integer $a_i$ means that $a_i$ is the parent of node $i+1$, and $a_i \le i$. - If no solution exists, output `NO`. If there are multiple valid answers, you may output any one of them. **In particular, if $n=1$ and a solution exists, output an empty line for the construction.**

### Sample Explanation For the second query of the second sample, $n=5, d=6, k=2$. That is, you need to construct a tree with $5$ nodes, where the sum of distances from all nodes to node $1$ is $6$, and every non-leaf node has at least $k$ child nodes. The following is the tree constructed in the sample:  The distances from nodes $1,2,3,4,5$ to the root node $1$ are $0,1,1,2,2$, respectively, and their sum is $6$, which satisfies the condition. Also, the non-leaf nodes $1$ and $3$ both have at least $2$ children. It can be proven that among all valid constructions, this one has the minimum possible maximum depth, which is $2$ here. ### Constraints **This problem uses bundled testdata.** |$\text{Subtask}$|Score|$n \le$|Special Properties| | :-----------: | :-------------:|:-----------: |:-----------: | |$0$|$5$|$10$|None| |$1$|$5$|$20$|None| |$2$|$5$|$10^5$|$k= n-1$| |$3$|$5$|$10^5$|$k= n-1$ or $n-2$| |$4$|$10$|$10^5$|$T=1$| |$5$|$70$|$10^5$|None| For all testdata, it is guaranteed that: $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}$. Translated by ChatGPT 5