Construct a tree
Contest: Codeforces Round 530 (Div. 1)
Difficulty rating: 2400
Tags: binary search, constructive algorithms, dfs and similar, graphs, greedy, trees

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 $$$p_i$$$, and $$$i$$$ is called a child of vertex $$$p_i$$$. Vertex $$$u$$$ belongs to the subtree of vertex $$$v$$$ iff $$$v$$$ is reachable from $$$u$$$ while iterating over the parents ($$$u$$$, $$$p_{u}$$$, $$$p_{p_{u}}$$$, ...). 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.

Input format:
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 \le n \le 10^5$$$; $$$1 \le s \le 10^{10}$$$).

Output format:
If the required tree does not exist, output «No». Otherwise output «Yes» on the first line, and in the next one output integers $$$p_2$$$, $$$p_3$$$, ..., $$$p_n$$$, where $$$p_i$$$ denotes the parent of vertex $$$i$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
3 5

Example output:
Yes
1 1

Example input:
4 42

Example output:
No

Editorial:
Note, that vertex belongs to subtrees of vertexes, which lay on its way to root. So, sum of sizes of subtrees is equal to $$$p + n$$$, where $$$p$$$ is sum of lengths of ways from root to vertexes. Let's consider which sum of sizes of subtrees can be in tree with branching coefficient less or equal than $$$k$$$.
Minimal sum can be achieved in $$$k$$$-nary tree (it consists of root, $$$k$$$ vertexes on distance $$$1$$$, $$$k^2$$$ on distance $$$2$$$, etc, the last level can be filled not completely).
Maximal sum can be achieved in bamboo — tree, which consists of only one way with length $$$n$$$. If $$$s$$$ is bigger than sum in this tree, the answer will be «No».
Let's find minimal $$$k$$$, such that $$$s$$$ is not smaller than sum of sizes of subtrees in $$$k$$$-nary tree (using binary search). Now $$$s$$$ is between minimal and maximal sum of sizes of subtrees in tree with branching coefficient, which is not bigger than $$$k$$$.
Let's show how to build tree with the given sum, which is between these two borders. Let's start with $$$k$$$-nary tree.
Let's realize recursive function, which rebuilds tree. Let we are in a subtree, and want to increase sum of sizes of subtrees by $$$x$$$ (in this subtree). We can change this subtree to bamboo with same number of vertexes (if the sum of sizeof of subtrees won't be too big). Otherwise, we run this function from subtrees in some order. If we reach needed sum, we will terminate the process. Otherwise, every subtree of child is bamboo now, current sum of sizes is smaller than needed, but if we merged bamboos, it would be bigger than it. Let's move vertexes to the end of the first bamboo from others. Over time, after next moving, sum of sizes will increase too much. We can move it to the another position in the first bamboo, in order to make sum equal to $$$s$$$, and terminate the process.
But if we believe that every tree with sum of sizes of subtrees between maximal and minimal can be built, there is another solution with $$$O(n \log n)$$$ complexity, which is easier to realize.
The sum of subtree sizes is influenced only by the number of vertices at each distance, and not by their mutual arrangement. Sum of sizes of subtrees is equal to $$$n + i \cdot d_{i}$$$, where $$$d_{i}$$$ — number of vertexes on distance $$$i$$$ from the root. Let's built this array of counts. These conditions must be satisfied:
• If the $$$i$$$-th element is bigger than $$$0$$$ ($$$i > 0$$$), than $$$i - 1$$$-th element must be bigger than $$$0$$$.
• If the $$$i$$$-th element is equal to $$$t$$$, $$$i + 1$$$-th mustn't be bigger than $$$t \cdot k$$$.
• Sum of elements must be equal to $$$n$$$.
Let we have recovered some prefix of this array (i.e we know that we can fill rest, and sum of sizes of subtrees will be equal to $$$s$$$). Let's try to put some value to the next element.
We know that the tree can be rebuilt so that the sum is any between maximum and minimum, so there are two conditions, which are satisfied (we want to put value $$$x$$$ to position $$$i$$$).
• $$$x$$$ must be big enough, so if we fill suffix with numbers $$$x$$$, $$$x \cdot k$$$, $$$x \cdot k^2$$$, ... (the last non-zero number can be smaller, sum of numbers is $$$n$$$) sum of sizes of subtrees will be not greater to $$$s$$$.
• $$$x$$$ must be small enough, so if we fill suffix with $$$1$$$, sum of sizes of subtrees will be not less than $$$s$$$.
Both borders form some segment of values, which could be put to this position. We haven't to look for the left border, just find the right border by binsearch, and put number, which is equal to it. We can easily restore the tree, using array $$$d$$$.