Codeforces 2120C Divine Tree

题目

原题链接 2120C Divine Tree

对于一个有 $n$ 个结点，编号分别从 $1$ 到 $n$ 的有根树，设某个结点为 $v$，定义 $d(v)$ 为从根到此结点路径上所有结点编号的最小值。

给定两个正整数 $n, m$，请构造出一个有 $n$ 个结点，编号分别从 $1$ 到 $n$ 的有根树，使得 $\sum_{i=1}^n d(i) = m$。如果不存在这样的树，输出 $-1$。

输入

第一行为一个整数 $t\ (1 \le t \le 10^4)$，表示数据的组数。

每组数据为一行两个整数 $n$ 和 $m \ (1 \le n \le 10^6, 1 \le m \le 10^12)$。

保证所有 $n$ 之和不超过 $10^6$。

输出

对于每组数据，第一行输出一个整数，表示树根。

接下来输出 $n-1$ 行，每行为两个整数 $u,v$，代表一条连接顶点 $u,v$ 的边。

边和顶点可以以任何顺序输出。如果有多种可能的解，输出任意一种。

如果不存在解，输出 $-1$。

样例

输入 #1

2
1 2
4 6

输出 #1

-1
3
3 1
1 2
2 4

分析

当 $n$ 和 $m$ 差距过大时，显然是无解的。具体范围是多少呢？有 $n$ 个结点时，要使 $\sum d(i)$ 最小，可以将 $1$ 作为根结点，这样所有结点的 $d$ 值都是 $1$，$m$ 下确界为 $n$；要使 $\sum d(i)$ 最大，可以将 $n$ 作为根结点，每个结点的 $d$ 值等于本身，$m$ 上确界为 $\frac{n(n+1)}{2}$。

先将 $1$ 作为树根，考虑调整一些结点让 $d$ 值总和变大，以调整至 $m$。若将结点 $v$ 连接至 $1$ 的上方，成为新的树根，则 $d$ 值总和变大 $v-1$，其他结点 $d$ 值不变。对于小于 $v$ 的结点，都可以直接连在 $1$ 的上方，而影响其他点的 $d$ 值。

因此从大的结点开始向前调整。每个结点只要调整后总 $d$ 值没有超过目标，就一定要调整，因为利用前面的结点达到相同的效果不会更优。这样的调整策略容易发现一定有解。

代码实现

先判断 $m$ 的范围，排除无解的情况。

最初总 $d$ 值为 $n$，减掉后从后往前标记需要调整的结点。同时找出树根（因为树根要第一个输出）。

m -= n;
int root = 1;
vector<int> v(n + 1);
for (int i = n; m && i > 1; i--) {
    // 能调整就调整
    if (i - 1 <= m) {
        m -= i - 1;
        v[i] = 1;
        if (root == 1) root = i;
    }
}

确定了哪些点被调整到了 $1$ 的上方后，输出所有边即可。

完整代码

#include <bits/stdc++.h>
using namespace std;
void solve(int n, long long m) {
    long long l = n, r = 1LL * n * (n + 1) / 2;
    if (m < l || m > r) {
        cout << "-1\n";
        return;
    }
    m -= n;
    int root = 1;
    vector<int> v(n + 1);
    for (int i = n; m && i > 1; i--) {
        if (i - 1 <= m) {
            m -= i - 1;
            v[i] = 1;
            if (root == 1) root = i;
        }
    }
    cout << root << '\n';
    int last = root;
    v[1] = 1;
    for (int i = n; i >= 1; i--) {
        if (!v[i]) {
            cout << i << " 1\n";
        } else if (i != root) {
            cout << i << ' ' << last << '\n';
            last = i;
        }
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        long long m;
        cin >> n >> m;
        solve(n, m);
    }
    return 0;
}