CodeForces 1311E Construct the Binary Tree

十月 19, 2020 2978

题意简述

给定一个 n 和 k，构造一棵以 1 为根的二叉树，使得每个点的深度之和恰好为 k。无解输出 Impossible。

解题思路

首先来判断一下有没有解。

显然，这个答案的上界是一条链的形态，下界是尽可能满的二叉树形态，链可以 O(1) 算，完全二叉树可以 O(n) 构造一下。

接着来考虑如何求解。

观察到 \sum n \leq 5000 ，所以我们可以直接从最小的深度和或者最大的深度和一点一点逼近 k。

这里讲一下怎么从完全二叉树逼近 k。

为了方便，我们构造完全二叉树的时候，编号从左到右从上到下增加。

为了尽可能地不错过答案，考虑一点一点地增加高度，也即每次高度和仅增加 1。

一个点要高度增加 1，肯定是要往另外一条链上跑的，这里我们为了方便，把 1 \rightarrow n 这条链拎出来。

接下来倒序枚举每个点，如果这个点在 1 到 n 的链上就不管，否则就让它连到 1 到 n 这条链上与它同高度的点，这时候这个点的深度增加了 1，深度和也增加了 1。

如果这个时候深度和达到 k 就直接退出，否则就继续让它往深了走，直到它成为链的另一个端点，就退出去继续枚举下一个点。

如果所有的操作都做完了，树已经成链了，仍然没有达到 k，就无解。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// Accepted

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>

#define DEBUG(x) std::cerr << #x << " = " << x << std::endl;
#define forall(G,u) for (int i_ = 0, __for_siz__ = (int) G[u].size(); i_ < __for_siz__; ++i_) 

using std::cin;
using std::cout;
using std::endl;

inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXN = 5000 + 10;

int n, d;
int fa[MAXN], dep[MAXN], nodedep[MAXN];
bool onchain[MAXN];

void cleanup() {
    memset(fa, 0, sizeof fa);
    memset(dep, 0, sizeof dep);
    memset(nodedep, 0, sizeof nodedep);
    memset(onchain, 0, sizeof onchain);
}

void constrCBT() {
    for (int i = 1; i <= n; ++i) {
        fa[i] = (i >> 1);
    }
    dep[1] = 0;
    for (int i = 2; i <= n; ++i) {
        dep[i] = dep[fa[i]] + 1;
    }
    int u = n;
    while (u) {
        onchain[u] = true;
        nodedep[dep[u]] = u;
        u = fa[u];
    }
}

int main() {
    int T = read();
    while (T --> 0) {
        n = read(); d = read();
        constrCBT();
        int sumdep = 0;
        for (int i = 1; i <= n; ++i) sumdep += dep[i];
        if (sumdep > d) { puts("NO"); cleanup(); continue; }
        for (int i = n; i >= 1 && sumdep != d; --i) {
            if (onchain[i]) continue;
            bool cont = true;
            while (cont && sumdep != d) {
                fa[i] = nodedep[dep[i]]; ++dep[i]; ++sumdep;
                if (!nodedep[dep[i]]) {
                    cont = false;
                    nodedep[dep[i]] = i;
                }
            }
        }
        if (sumdep == d) {
            puts("YES");
            for (int i = 2; i <= n; ++i) {
                printf("%d ", fa[i]);
            }
            puts("");
        } else puts("NO");
        cleanup();
    }
    return 0;
}