题目链接 --> Problem - E - Codeforces

题目大意

给定 \(n\) 和 \(d\)，你需要构造一棵 \(n\) 个点的二叉树

满足所有点的深度之和恰好为 \(d\)。\(2≤n,d≤5000\)。

分析

• 首先考虑深度最小的情况，也就是完全二叉树。如果 \(d\) 小于这个数，则直接输出 "NO"。

• 否则，我们考虑对这棵树进行修改，每次让总深度 \(+1\)。

• 首先，随便拎出来一条最深的链，此处我们选择 \(1\) 到 \(n\)。

• 然后我们开始倒序考虑不在这条链上的所有点，每次尝试把这个点的深度 \(+1\)。

• 只需要让这个点的父节点变为链上深度等于它的节点即可。

• 因为在深度之和没有达到 \(d\) 的时候当前节点会一直向下走，直到不能继续，所以实际上并不会破坏二叉树的性质。

• 而且每次我们刚好把总深度 \(+1\)，所以一定能够得到所有可行的结果。

• 如果最后还没达到 \(d\) 那就不可能构造，输出 "NO"。

Code

int n, d, mx, a[N], dep[N], fa[N];
bool st[N];

void solve() {
    cin >> n >> d;
    memset(st, 0, sizeof(st));
    mx = 0, a[0] = 1;
    for (int i = 2; i <= n; i++) {
        fa[i] = i / 2;
        dep[i] = dep[fa[i]] + 1;
        d -= dep[i];
        mx = max(mx, dep[i]);
    }

    // 考虑深度最小的情况，也就是完全二叉树。
    if (d < 0) {
        cout << "NO" << endl;
        return;
    }

    // 随便找出一条最深的链（此处1 - n），并标记在这条链上的点。
    int tmp = n;
    while (tmp) {
        a[dep[tmp]] = tmp, st[tmp] = true;
        tmp = fa[tmp];
    }

    // 倒序考虑不在这条链上的所有点。
    for (int i = n; i >= 1; i--) {
        if (st[i])  continue;

        int pre = mx;
        while (dep[fa[i]] < pre && d) {
            // 每次尝试把这个点的深度 +1   -->   让这个点的父节点变为之前选的链上深度等于它的节点
            fa[i] = a[dep[fa[i]] + 1];
            dep[i] = dep[fa[i]] + 1;
			
            // 相当于接到最深那一层
            if (dep[i] > mx)    mx++, a[mx] = i, st[i] = true;
            
            d--;
        }
    }
    if (d) {
        cout << "NO" << endl;
        return;
    }
    
    cout << "YES" << endl;
    for (re int i = 2; i <= n; i++) cout << fa[i] << " ";
    cout << endl;
    return;
}