CF1098C.Construct a tree
提高+/省选-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Misha walked through the snowy forest and he was so fascinated by the trees to decide to draw his own tree!
Misha would like to construct a rooted tree with n vertices, indexed from 1 to n, where the root has index 1. Every other vertex has a parent pi, and i is called a child of vertex pi. Vertex u belongs to the subtree of vertex v iff v is reachable from u while iterating over the parents (u, pu, ppu, ...). Clearly, v belongs to its own subtree, and the number of vertices in the subtree is called the size of the subtree. Misha is only interested in trees where every vertex belongs to the subtree of vertex 1.
Below there is a tree with 6 vertices. The subtree of vertex 2 contains vertices 2, 3, 4, 5. Hence the size of its subtree is 4.

The branching coefficient of the tree is defined as the maximum number of children in any vertex. For example, for the tree above the branching coefficient equals 2. Your task is to construct a tree with n vertices such that the sum of the subtree sizes for all vertices equals s, and the branching coefficient is minimum possible.
米沙穿行于雪林之中,被树木深深吸引,于是决定亲手绘制一棵属于自己的树!
米沙希望构造一棵含有 n 个顶点的有根树,顶点编号为 1 至 n,其中根节点编号为 1。其余每个顶点 i 均有一个父节点 pi,此时称 i 是顶点 pi 的一个子节点。若从顶点 u 出发,不断沿父节点向上遍历(即依次访问 u、pu、ppu、……),最终可到达顶点 v,则称顶点 u 属于顶点 v 的子树。显然,顶点 v 自身属于其自身的子树;该子树中所含顶点的总数称为该子树的大小。米沙只关心那些所有顶点均属于顶点 1 的子树的树(即整棵树以 1 为根的连通树)。
下图展示了一棵含 6 个顶点的树。顶点 2 的子树包含顶点 2、3、4、5,因此其子树大小为 4。

该树的分支系数定义为所有顶点中子节点数的最大值。例如,上图所示树的分支系数为 2。你的任务是构造一棵含 n 个顶点的树,使得所有顶点的子树大小之和恰好等于 s,且分支系数尽可能小。
输入格式
The only input line contains two integers n and s — the number of vertices in the tree and the desired sum of the subtree sizes (2≤n≤105; 1≤s≤1010).
唯一的一行输入包含两个整数 n 和 s —— 分别表示树的顶点数以及期望的子树大小之和(2≤n≤105;1≤s≤1010)。
输出格式
If the required tree does not exist, output «No». Otherwise output «Yes» on the first line, and in the next one output integers p2, p3, ..., pn, where pi denotes the parent of vertex i.
如果所要求的树不存在,则输出“No”。否则,第一行输出“Yes”,第二行输出整数 p2, p3, ..., pn,其中 pi 表示顶点 i 的父节点。
输入输出样例
输入#1
3 5
输出#1
Yes 1 1
输入#2
4 42
输出#2
No
输入#3
6 15
输出#3
Yes 1 2 3 1 5
说明/提示
Below one can find one of the possible solutions for the first sample case. The sum of subtree sizes equals 3+1+1=5, and the branching coefficient equals 2.

Below one can find one of the possible solutions for the third sample case. The sum of subtree sizes equals 6+3+2+1+2+1=15, and the branching coefficient equals 2.

下面给出了第一个样例的一种可能解。子树大小之和为 3+1+1=5,分支系数为 2。

下面给出了第三个样例的一种可能解。子树大小之和为 6+3+2+1+2+1=15,分支系数为 2。

输入解题思路,AI测评打分。不知道怎么写?