CF2120C Divine Tree 题解

yyrwlj · 2025-06-24 22:46:30 · 题解

跟这题一个道理。

下文令 s = \sum d(i)。

考虑根为 i 的树，要让其 s 最大，可以构造菊花图，则 s = \frac{(1+i)i}{2}+(n-i)i；让其 s 最小，可以让除了根和 1 以外的所有点全接到 1 的下面，则 s = i+n-1。

知道了上下界，大胆猜测 s 能取到上下界中的任意整数，可以进行简单证明：

初始状态为菊花图，从大到小考虑除根和 1 以外的点 x，让它的父节点从根变成一个挂在根下面的编号小于 x 的点 y，s 会减少 \min(i,x)-\min(i,y)。

由于我们从大到小考虑，所以 x 能接到 [1,x-1] 中的任意一个 y 下面，即 s 减少的值能取到 [1,\min(i,x)-1] 中的任意整数，进而 s 能取到上下界中的任意整数，证毕。

回到题目，先选定一个根节点使得 m 在其 s 的上下界之间，接下来的构造方式可以参考证明方式：

初始状态为菊花图，从大到小考虑除根和 1 以外的点 x，如果还需要调整的值即 s-m 大于能给 s 减少的最大值即 \min(i,x)-1，则直接接到 1 下面，否则接到点 y 下面使得 \min(i,x)-y=s-m，即接到点 y=\min(i,x)+m-s 下面，构造结束。

#include <bits/stdc++.h>
#define lowbit(o) o & -o
#define pb push_back
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int N = 1000005;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const LL INF = 2e18;
LL fa[N];
void work()
{
    LL n, m;
    cin>>n>>m;
    LL rt = -1;
    for (LL i=1;i<=n;i++)
    {
        LL l = i + n - 1, r = (1 + i) * i / 2 + (n - i) * i;
        if (l <= m && m <= r)
        {
            rt = i;
            break;
        }
    }
    if (rt==-1){
        cout<<"-1\n";
        return;
    }
    for (int i=1;i<=n;i++)
        fa[i] = rt;
    LL s = (1 + rt) * rt / 2 + (n - rt) * rt;
    for (LL i=n;i>1;i--)
    {
        if (s == m)
            break;
        LL v = min(rt, i);
        if (s - (v - 1) <= m)
        {
            LL id = m - s + v;
            // s - v + x = m
            fa[i] = id;
            s -= v - id;
            break;
        }
        fa[i] = 1;
        s -= v - 1;
    }
    cout << rt<<'\n';
    for (int i=1;i<=n;i++)
        if (i != rt)cout<<fa[i]<<' '<<i<<'\n';

}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int _T = 1;
    cin >> _T;
    while (_T--)
        work();
    return 0;
}