题解：CF2162G Beautiful Tree

zjc5 · 2025-10-30 10:51:29 · 题解

题目链接

首先可以考虑一个菊花，设其中间的点为 a，则 S=a(\frac{n(n+1)}{2}-a)。

由于要求 S 是平方数，考虑将 a 设为 2 消去分母的 2，则 S=n(n+1)-4=n^2+n-4。

要使这棵树的 S 减少 n-4，于是将 n-4 号节点从 2 号节点改接到 1 号节点。

能进行上述操作的条件是 n-4\gt2，所以对于 n\ge7 都有解，其余的直接打表。

#include<bits/stdc++.h>
using namespace std;
signed main(){
    int T;cin>>T;
    while(T--){
        int n;cin>>n;
        if(n==2) puts("-1");
        else if(n==3) puts("1 3\n2 3");
        else if(n==4) puts("1 2\n1 3\n1 4");
        else if(n==5) puts("3 1\n1 4\n4 2\n2 5");
        else if(n==6) puts("6 4\n4 5\n5 3\n3 1\n1 2");
        else {
            for(int i=1;i<=n;i++)
                if(i!=2){
                    if(i==n-4) cout<<"1 "<<i<<"\n";
                    else cout<<"2 "<<i<<"\n";
                }
        }
    }
    return 0;
}