题解：CF2120C Divine Tree

CommandSR · 2025-07-09 19:54:13 · 题解

题面

link

题解

先确定无解情况，要求的答案最小情况下是 n 个 1，即 n，最大情况下是从 n 到 1 各一个，即 \frac{n \times (n+1)}{2}，若 m 在 [n, \frac{n \times (n+1)}{2}] 范围之外则无解。

考虑简化问题直接构造一条链。不妨先给每个点分发一个 divineness 为 d_i，再根据 d_i 构造。

分发的过程是先尝试给每个点分一个 1，如果 m 没用完就给 [2, n] 的点改成 2，如果还没用完就给 [3, n] 的点改成 3，直到 m 用完为止。

分配完 divineness 之后给所有 d_i 从小到大排个序（我的代码已保证有序），把 [d_n + 1, n] 扔到一个“垃圾桶”，它们不作为权值。

然后显然根节点必须是 d_n，之后的每个点如果 d_i 之前没用过就接上 d_i，否则就从“垃圾桶”翻东西接上，显然这样构造和 d 数组规定的权值相符。且可以保证每个点都不重不漏接上。

Code

const int N = 1e6 + 5;
ll a[N];
void GOGOGO() {
    ll n = rd(), m = rd(), ac = 0;
    if (m < n || m > n*(n+1)/2) {cout << "-1\n"; return;}
    F(i, 1, n) { // 分配权值
        if (m > n - i + 1) m -= n - i + 1, a[++ac] = i;
        else {
            F(j, i, n - m) a[++ac] = i-1;
            F(j, n - m + 1, n) a[++ac] = i;
            break;
        }
    }
    ll rub = a[n] + 1, pre = a[n]; // rub 是 “垃圾桶”
    cout << a[n] << '\n';
    D(i, n-1, 1) {
        if (a[i] == a[i+1]) cout << pre << ' ' << (pre = rub++) << '\n';
        else cout << pre << ' ' << (pre = a[i]) << '\n';
    }
}