CF1311E Construct the Binary Tree 题解

题意：

要求构造一个 $n$ 个节点的二叉树（每个节点拥有不超过 $2$ 个孩子），节点 $1$ 为根，要使所有节点到根的距离之和为 $d$ 。要求先判断可不可以构造，如果可以输出 YES ，下一行输出 2 到 n 号节点的父亲节点，否则输出 NO 。有多组询问。

输入格式：

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$ ).

输出格式：

For each test case, print the answer.

If it is impossible to construct such a tree, print NO 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.

这里讲一种线性的构造方法。详见参考文献 [1]

首先能构造的最小值一定是棵满二叉树的形式（国内定义），而最大值一定是一条链。

更一般的情况，若合法，则一定可以从满二叉树通过向链调整得到。

为啥呢？因为合法啊，~~不然你觉得长啥样啊~~。

于是我们先构造最小值，记 $r$ 为剩余的要增加的深度，链的最下端为 $p$ 。

然后每次将编号最大的且不在主链上的点 $i$ （钦定 $2^k(k\in \mathbb{N})$ 为主链）插到主链上

若 $r \le (\mathtt{dep}(p) + 1)-\mathtt{dep}(i)$ ，那么 $i$ 需要成为 $p$ 的第 $\mathtt{dep}(p) + 1 - \mathtt{dep}(i) - r$ 个父亲

然后令 $r \gets r-(\mathtt{dep}(p) + 1-\mathtt{dep}(i))$ ，继续考虑下一个点。

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5+15))

int n,sum,fa[N],dep[N];
void pt() { for(int i=2; i<=n; i++) cout << fa[i] << " \n"[i==n]; }
void work()
{
    cin >> n >> sum; int cur = 0, pos; dep[0] = -1; 
    for(int i=1; i<=n; i++) 
    {
        dep[i] = dep[fa[i] = i >> 1] + 1; cur += dep[i];
        if((i & (i-1)) == 0) pos = i;
    }
    sum -= cur;
    if(sum < 0) { return cout << "NO\n", void(0); }
    if(sum == 0) { return cout << "YES\n", pt(); }
    for(int i=n; i; i--)
    {
        if((i & (i-1)) == 0) continue;
        sum -= dep[pos] + 1 - dep[i];
        if(sum <= 0)
        {
            while(sum != 0) pos = fa[pos], ++sum;
            sum = 0; fa[i] = pos; break;
        }
        fa[i] = pos; dep[i] = dep[pos] + 1; pos = i;
    }
    if(sum) cout << "NO\n";
    else
    { cout << "YES\n", pt(); }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int _Q; cin >> _Q; while(_Q--) work();
    return 0;
}