题解 | #小红的树构造#

题目中 个结点的树，设有 个非叶子结点。

1. 整棵树的结点的度数和为 ，有 个叶子结点，则 个结点的度数和为 度。

   题目要求 ，也就是说每个非叶子结点的度数均为k的倍数，即 。

   那么 则为 。

   设为 倍，则 。

   此时便可枚举 ，求出不同的 。

   然后将其中 个结点的度数构造为 ，其余的叶子结点连到最后一个结点上。

2. 考虑非法情况。

   首先不能存在 的情况，此时枚举的 过小，直接跳过。

   然后考虑 个结点的度数均为 ，此时叶子结点数量为 ，应限制不会超过 。

3. 开始构造。

   首先将 个非叶子结点 链接，然后将 号结点和之后的 个结点相连， 号结点每个需要连接 个点，最后将剩余所有的点均连到 号结点上。

   但是我们现在选的 并不能保证构造出来的一定正确，所以需要在构造完之后再 一遍，若构造出来的度数不合法，需要 continue。

   度数合法则输出 Yes 并输出构造方案。

   枚举完所有的 ，若均不存在合法构造，输出 No。

4. 此外，还有 的特殊情况。

   时，显然没有任何合法构造。

   时，，构造出

   

   当 时，，将 结点连接在 号结点上即可。

5. 完整代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int gcd(int a, int b)
{// 手写gcd
    return b ? gcd(b, a % b) : a;
}
vector<int> deg;
int check(vector<pair<int, int>> &a, int n)
{// 检查构造的是否合法
    deg.assign(n + 1, 0);
    for (auto [u, v] : a)
        deg[u]++, deg[v]++;
    int g = 0;
    for (int i = 1; i <= n; i++)
        if (deg[i] > 1)
            g = gcd(g, deg[i]);
    return g;
}
void _()
{
    int n, k;
    cin >> n >> k;
    if (k == 1)
    {// 特判
        if (n < 5)
            cout << "No\n";
        else
        {
            cout << "Yes\n";
            cout << 1 << ' ' << 2 << '\n';
            cout << 1 << ' ' << 3 << '\n';
            cout << 2 << ' ' << 4 << '\n';
            cout << 2 << ' ' << 5 << '\n';
            for (int i = 6; i <= n; i++)
                cout << 5 << ' ' << i << '\n';
        }
        return;
    }
    for (int x = ceil(1.0 * (n - 2) / k), m = x * k + 2 - n; 2 * (k - 1) + (m - 2) * (k - 2) <= n - m; x++, m = x * k + 2 - n)
    {// 枚举 x
        if (m < 1)
            continue;
        vector<pair<int, int>> ans;
        for (int i = 1; i < m; i++)
            ans.push_back(make_pair(i, i + 1));
        int cnt = m + 1;
        for (int j = 2; j <= k; j++)
            ans.push_back(make_pair(1, cnt++));
        for (int i = 2; i <= m; i++)
            for (int j = 2; j < k; j++)
                ans.push_back(make_pair(i, cnt++));
        while (cnt <= n)
            ans.push_back(make_pair(m, cnt++));
        if (k != check(ans, n))
            continue;
        cout << "Yes\n";
        for (auto [u, v] : ans)
            cout << u << ' ' << v << '\n';
        return;
    }
    cout << "No\n";
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
        _();
    return 0;
}