Construct the Binary Tree (Codeforces 1311E)
Tags: Others, trees

You are given two integers $$$n$$$ and $$$d$$$. You need to construct a rooted binary tree consisting of $$$n$$$ vertices with a root at the vertex $$$1$$$ and the sum of depths of all vertices equals to $$$d$$$.A tree is a connected graph without cycles. A rooted tree has a special vertex called the root. A parent of a vertex $$$v$$$ is the last different from $$$v$$$ vertex on the path from the root to the vertex $$$v$$$. The depth of the vertex $$$v$$$ is the length of the path from the root to the vertex $$$v$$$. Children of vertex $$$v$$$ are all vertices for which $$$v$$$ is the parent. The binary tree is such a tree that no vertex has more than $$$2$$$ children.You have to answer $$$t$$$ independent test cases.

Input: The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.The only line of each test case contains two integers $$$n$$$ and $$$d$$$ ($$$2 \le n, d \le 5000$$$) — the number of vertices in the tree and the required sum of depths of all vertices.It is guaranteed that the sum of $$$n$$$ and the sum of $$$d$$$ both does not exceed $$$5000$$$ ($$$\sum n \le 5000, \sum d \le 5000$$$).

Output: For each test case, print the answer.If it is impossible to construct such a tree, print "NO" (without quotes) in the first line. Otherwise, print "{YES}" in the first line. Then print $$$n-1$$$ integers $$$p_2, p_3, \dots, p_n$$$ in the second line, where $$$p_i$$$ is the parent of the vertex $$$i$$$. Note that the sequence of parents you print should describe some binary tree.

Note: Pictures corresponding to the first and the second test cases of the example:

Sample Inputs:
3
5 7
10 19
10 18

Sample Outputs:
YES
1 2 1 3 
YES
1 2 3 3 9 9 2 1 6 
NO

Solution (Python):
def solve(n, d):
    arr = [[x] for x in range(1, n + 1)]
    S = sum(range(1, n))
    cur = 1
    while S > d and cur != len(arr):
        need = S - d
        can = len(arr) - 1 - cur
        if can < need:
            S -= can
            arr[cur] += arr[-1]
            arr.pop()
        else:
            S -= need
            arr[len(arr) - 1 - need] += arr[-1]
            arr.pop()
        if cur == len(arr):
            break
        elif len(arr[cur]) == 2 ** cur:
            cur += 1
    if S != d:
        print('NO')
    else:
        print('YES')
        ans = [0] * (n - 1)
        for (i, a) in enumerate(arr):
            if i == 0:
                continue
            for (j, v) in enumerate(a):
                ans[v - 2] = str(arr[i - 1][j // 2])
        print(' '.join(ans))
for _ in range(int(input())):
    (n, d) = map(int, input().split())
    solve(n, d)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.readline())

def MI():
    return map(int, sys.stdin.readline().split())

def LI():
    return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def SI():
    return sys.stdin.readline()[:-1]

def main():
    t = II()
    for _ in range(t):
        (n, d) = MI()
        s = n * (n - 1) // 2
        diff = s - d
        if d > s:
            print('NO')
            continue
        aa = [1] * n
        l = 1
        for r in range(n - 1, -1, -1):
            if l >= r:
                break
            if diff == 0:
                break
            to = max(r - diff, l)
            aa[r] = 0
            aa[to] += 1
            diff -= r - to
            if aa[l] == 1 << l:
                l += 1
        if diff:
            print('NO')
            continue
        ans = []
        pa = 1
        st = 1
        for a in aa[1:]:
            for i in range(a):
                ans.append(st + i % pa)
            st += pa
            pa = a
        print('YES')
        print(*ans)
main()

Solution (Python):
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    (n, d) = map(int, input().split())
    max = n * (n - 1) // 2
    if d > max:
        print('NO')
        continue
    dif = max - d
    tree = [1] * n
    (move_to, move_from) = (1, n - 1)
    while move_from > move_to:
        if dif > move_from - move_to:
            tree[move_from] -= 1
            tree[move_to] += 1
            dif -= move_from - move_to
        else:
            tree[move_from] -= 1
            tree[move_from - dif] += 1
            dif = 0
            break
        if tree[move_to] == 2 ** move_to:
            move_to += 1
        if tree[move_from] == 0:
            move_from -= 1
    if dif > 0:
        print('NO')
        continue
    print('YES')
    (ans, ind) = ([[1]], 2)
    for i in range(1, n):
        ti = []
        for j in range(tree[i]):
            ti.append(ind)
            ind += 1
        ans.append(ti)
    answ = []
    for i in range(1, n):
        for j in range(tree[i]):
            answ.append(ans[i - 1][j // 2])
    print(*answ)