{"problem":{"name":"「Daily OI Round 1」Tree","description":{"content":"给定三个正整数参数 $n,d,k$，你需要构造出一棵根节点为 $1$ 的树，满足这棵树有 $n$ 个节点，每个节点到根节点的距离和为 $d$，除了叶节点以外每个节点的**直接**儿子数量**至少** $k$ 个，且所有节点的最大深度最小。 **注意事项：** - 距离：两个点之间的简单路径上的边的条数。 - 叶子节点：没有儿子的非根节点。 - 根节点深度为 $0$。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9592"},"statements":[{"statement_type":"Markdown","content":"给定三个正整数参数 $n,d,k$，你需要构造出一棵根节点为 $1$ 的树，满足这棵树有 $n$ 个节点，每个节点到根节点的距离和为 $d$，除了叶节点以外每个节点的**直接**儿子数量**至少** $k$ 个，且所有节点的最大深度最小。\n\n**注意事项：**\n\n- 距离：两个点之间的简单路径上的边的条数。\n- 叶子节点：没有儿子的非根节点。\n- 根节点深度为 $0$。\n\n## Input\n\n**本题有多组数据。**  \n\n第一行一个正整数 $T$，表示数据组数。  \n对于每组数据：共一行三个正整数 $n,d,k$，含义如题所示。\n\n## Output\n\n对于每次询问，如果有解，第一行输出 `YES`，然后一行 $n-1$ 个正整数，第 $i$ 个正整数 $a_i$ 表示 $a_i$ 是 $i+1$ 的父亲节点，且 $a_i\\leq i$；如果无解，输出 `NO`。\n\n如果有多组合法的答案，可以任意输出其中一组。\n\n**特别地，如果 $n=1$ 且有解，方案输出一行空行即可。**\n\n[samples]\n\n## Note\n\n### **样例解释**\n\n对于第二组样例的第二组询问，$n=5,d=6,k=2$，即需要构造出含有 $5$ 个节点，各个节点到节点 $1$ 的距离和为 $6$ 且除叶节点外的节点至少有 $k$ 个儿子节点。\n\n下面是样例构造的图：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/wgir5yt5.png)\n\n其中编号为 $1,2,3,4,5$ 的点到根节点 $1$ 的距离分别为 $0,1,1,2,2$，和为 $6$，满足条件。而且非叶子节点 $1,3$ 都含有至少 $2$ 个儿子节点，可以证明这是所有合法构造中节点的最大深度最小的解法，在此处为 $2$。\n\n### **数据范围**\n  \n**本题开启捆绑测试。**\n\n|$\\text{Subtask}$|分值|$n \\le$|特殊性质|\n| :-----------: | :-------------:|:-----------: |:-----------: |\n|$0$|$5$|$10$|无|\n|$1$|$5$|$20$|无|\n|$2$|$5$|$10^5$|$k= n-1$|\n|$3$|$5$|$10^5$|$k= n-1$ 或 $n-2$|\n|$4$|$10$|$10^5$|$T=1$|\n|$5$|$70$|$10^5$|无|\n\n对于全部数据，保证：$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}$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9592","tags":["洛谷原创","Special Judge","O2优化","构造"],"sample_group":[["3\n5 4 1\n5 6 1\n5 7 1","YES\n1 1 1 1\nYES\n1 1 3 3\nYES\n1 2 2 2"],["3\n5 4 2\n5 6 2\n5 7 2","YES\n1 1 1 1\nYES\n1 1 3 3\nNO"]],"created_at":"2026-03-03 11:09:25"}}