CF1098C Construct a tree 题解

题意：

Misha 在雪地森林中漫步，他对树木如此着迷，以至于决定自己绘制一棵树！

Misha 想构造一棵有 \(n\) 个顶点的有根树，顶点从 \(1\) 到 \(n\) 编号，其中根的编号为 \(1\)。每个其他顶点都有一个父节点 \(p_i\)，且 \(i\) 是顶点 \(p_i\) 的子节点。顶点 \(u\) 属于顶点 \(v\) 的子树，当且仅当从 \(u\) 开始通过父节点（\(u\), \(p_{u}\), \(p_{p_{u}}\), ...）可以到达 \(v\)。显然，\(v\) 属于它自己的子树，子树中的顶点数量称为子树的大小。Misha 只对每个顶点都属于顶点 1 的子树的树感兴趣。

下面是一个有 6 个顶点的树。顶点 2 的子树包含顶点 2、3、4、5。因此其子树的大小是 4。

树的分支系数定义为任意顶点的最大子节点数。例如，上述树的分支系数为 2。你的任务是构造一棵有 \(n\) 个顶点的树，使所有顶点的子树大小之和等于 \(s\)，并且分支系数尽可能小。

输入格式

唯一的输入行，包含两个整数 \(n\) 和 \(s\) 。

树的顶点数量和所需的子树大小之和（\(2 \le n \le 10^5\)；\(1 \le s \le 10^{10}\)）。

输出格式：

如果所需的树不存在，则输出 No。

否则在第一行输出 Yes，接下来一行输出整数 \(p_2\)，\(p_3\)，...，\(p_n\)，其中 \(p_i\) 表示顶点 \(i\) 的父节点。

这道题类似于 CF1311E Construct the Binary Tree 。

首先子树大小的和可以转化为每个节点的深度的和。

因为要求度数最小的方案，考虑二分最大度数 \(k\) 。显然度数越小，子树和越大。

由于深度最小的完全 \(k\) 叉树的深度和最小，所以对于合法的 \(k\) ，我们可以从最小的情况扩展。

考虑记录每个深度的节点的个数，以及每个节点的深度。考虑从深度最深的节点开始扩展即可。

时间复杂度 \(\mathcal{O}(n \log 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 rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e6 + 15))

int n, k, d[N], cnt[N];
bool check(int x)
{
    int tmp = 1, dep = 0, num = k - n;
    rep(i, 0, n) d[i] = cnt[i] = 0;
    for(int i = 2; i <= n; )
    {
        tmp *= x; ++dep;
        for(int j = 1; j <= tmp && i <= n; i++, j++) {
            ++cnt[dep]; d[i] = dep; num -= dep;
        }
        if(num < 0) return false;
    }
    for(int j = n; num; )
    {
        ++dep; if(cnt[d[j]] == 1) --j;
        down(tmp = num, dep - d[j]);
        --cnt[d[j]]; d[j] += tmp;
        ++cnt[d[j]]; num -= tmp; --j;
    }
    return true;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> k;
    if(k < 2 * n - 1 || k > n * (n + 1) / 2) return cout << "No\n", 0;
    int l = 1, r = n;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        check(mid) ? r = mid : l = mid + 1;
    }
    check(l); cout << "Yes" << '\n';
    d[1] = 0; sort(d + 2, d + 1 + n); rep(i, 0, n) cnt[i] = 0;
    for(int i = 2, j = 1; i <= n; i++)
    {
        while(d[j] != d[i] - 1 || cnt[j] == l) ++j;
        cout << j << " \n"[i == n]; ++cnt[j];
    }
    return 0;
}