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;
}