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