Construct a tree[CodeForces - 1098C]

​

能否構造出一棵 個節點的樹，使得以每個點為根的子樹的大小加起來等于，如果能，輸出使得兒子最多的點的兒子數目最少的那種。

邊界：菊花是子樹和最小的構造方法，鍊是子樹和最大的構造方法，也就是說下界為上界為

對于兒子最多的點的兒子數最少，也即要求最小是幾叉樹，考慮對于叉樹，不難得出完全叉樹是使得子樹和最小的構造方法，并且叉樹的子樹和比叉樹的子樹和下界更小，設個結點的完全叉樹的子樹和為，如果，那麼得考慮叉樹，若，那就是可以構造出

貢獻：每個結點對子樹和的貢獻是其祖先結點個數，也即它的深度

構造：确定好是叉樹的情況下，考慮先構造出一棵完全叉樹，此時可能還未達到要求的子樹和，考慮不停地使其子樹和增加，首先保證完全叉樹最左邊的鍊不被破壞，将此時最下面一層的結點放到最左邊的鍊下，增長其鍊長，這麼做，最開始的結點深度僅加1，不會有太大的貢獻，之後再将剩下的結點也如此做，最左邊的鍊會越來越長，而每次增加鍊長對子樹和的貢獻也會越來越大，而如果不是增加鍊長，而是選擇将其連在鍊上某點下，會發現結點深度會是從到的一個連續區間，當增加鍊長貢獻超過剩餘要求的子樹和時，一定可以在鍊中選擇某點，将其連在該點下剛好使得剩餘要求的子樹和為0

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn = 100005;
ll n, s, l, r, b;
ll d[maxn], cnt[maxn], sn[maxn];
ll get_mi (int k) //完全k叉樹
{
    ll t = n - 1, dep = 1, res = 1;
    d[0] = 1, d[1] = k;
    while (t > d[dep]) {
        res += d[dep] * (dep + 1);
        t -= d[dep++];
        d[dep] = d[dep - 1] * k;
    }
    res += t * (dep + 1);
    return res;
}
void solve (int k)
{
    ll t = s - 1, dep = 1, dn = k;
    cnt[d[1] = 1] = 1;
    ll i = 2;
    while (i <= n) {
        ++dep;
        for (int j = 1; i <= n && j <= dn; ++i, ++j)    ++cnt[d[i] = dep], t -= dep;
        dn *= k;
    }
    i = n;
    while (t) {
        ++dep;
        if (cnt[d[i]] == 1) --i;
        ll de = min(t, dep - d[i]);
        --cnt[d[i]];
        d[i] += de;
        ++cnt[d[i]];
        t -= de;
        --i;
    }
}
int main ()
{
    cin >> n >> s;
    l = 2 * n - 1, r = (n + 1) * n / 2;
    if (s < l || s > r) {
        cout << "No" << endl;
        return 0;
    }
    cout << "Yes" << endl;
    for (int i = 2; i <= n - 1; ++i)
        if (s >= get_mi(i)) {
            b = i;
            break;
        }
    solve(b);
    sort(d + 1, d + n + 1);
    int p = 1;
    for (int i = 2; i <= n; ++i) {
        while (d[p] != d[i] - 1 || sn[p] == b)  ++p;
        cout << p << " ";
        ++sn[p];
    }
    return 0;
}      

如有哪裡講得不是很明白或是有錯誤，歡迎指正

如您喜歡的話不妨點個贊收藏一下吧