专栏文章

题解：CF2162G Beautiful Tree

zzjc5
CF2162G题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mingft4u
此快照首次捕获于
2025/12/02 02:00
3 个月前
此快照最后确认于
2025/12/02 02:00
3 个月前
查看原文
题目链接
首先可以考虑一个菊花，设其中间的点为 aa，则 S=a(n(n+1)2−a)S=a(\frac{n(n+1)}{2}-a)。
由于要求 SS 是平方数，考虑将 aa 设为 22 消去分母的 22，则 S=n(n+1)−4=n2+n−4S=n(n+1)-4=n^2+n-4。
要使这棵树的 SS 减少 n−4n-4，于是将 n−4n-4 号节点从 22 号节点改接到 11 号节点。
能进行上述操作的条件是 n−4>2n-4\gt2，所以对于 n≥7n\ge7 都有解，其余的直接打表。
CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...