题解：CF2162G Beautiful Tree
Magallan_forever
·
·
题解
简要说明题意：
给出 n，构造一棵含 n 个节点的树。一条边 (u,v) 的权为 uv，要求树的边权之和是一个完全平方数。
题目分析：
想构造的方便一点，那我们构造的值最好是一个和 n 有关的东西。由于 1+3+5+\dots+(2n-1)=n^2，所以想到把奇数和偶数分成两堆，大于 2 的偶数和 1 连接，大于 1 的奇数和 2 连接。
至于为什么不是奇数和 1，偶数和 2，我一开始也是这么构造的，式子会麻烦一些。 :(
##### 偶数
记 $n=2k$，这个森林的和是 $3k^2+k-4$。
那我们连接 $(k-1,k)$（还可以把两棵树连起来），配凑一个 $k*(k-1)$，得到 $4k^2-4$，再将 $(1,4)$ 改为 $(2,4)$，得到了一个和为 $4k^2=n^2$ 的构造。
##### 奇数
记 $n=2k-1$，和为 $3k^2-k-4$。
连接 $(k,k+1)$ 得到 $4k^2-4$，同理将 $(1,4)$ 改为 $(2,4)$，得到一个和为 $4k^2=(n+1)^2$ 的构造。
然后注意一下 `corner case`。
##### 偶数
$n=2$ 应该是 `-1`。
$k=2,3$，即 $n=4,6$ 时，$(k-1,k)$ 会和 $(2,3)$ 重复。
$k=4,5$，即 $n=8,10$ 时，$(k-1,k),(2,4),(2,k)/(2,k-1)$ 会成环。
##### 奇数
同理，需要单独构造一下 $n=3,5,7$。
梳理后感觉构造过程并不复杂，可是半夜做题让我多花了很多时间计算和查错。:(
代码如下：
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int T,n;
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
cin>>T;
while(T--){
cin>>n;
if(n==2){
cout<<"-1\n";
continue;
}
if(n==6){
cout<<"1 2\n";
cout<<"1 3\n";
cout<<"1 5\n";
cout<<"1 6\n";
cout<<"4 5\n";
continue;
}
if(n==8){
cout<<"1 2\n";
cout<<"1 3\n";
cout<<"1 4\n";
cout<<"1 5\n";
cout<<"1 6\n";
cout<<"1 8\n";
cout<<"3 7\n";
continue;
}
if(n==10){
cout<<"1 2\n";
cout<<"1 3\n";
cout<<"1 4\n";
cout<<"1 5\n";
cout<<"1 6\n";
cout<<"1 7\n";
cout<<"1 8\n";
cout<<"1 9\n";
cout<<"2 10\n";
continue;
}
if(!(n&1)){
cout<<(n>>1)-1<<' '<<(n>>1)<<'\n';
cout<<"2 4\n";
for(int i=6;i<=n;i+=2) cout<<"1 "<<i<<'\n';
for(int i=3;i<=n;i+=2) cout<<"2 "<<i<<'\n';
continue;
}
if(n==3){
cout<<"1 3\n";
cout<<"2 3\n";
continue;
}
if(n==5){
cout<<"1 3\n";
cout<<"2 3\n";
cout<<"3 4\n";
cout<<"3 5\n";
continue;
}
if(n==7){
cout<<"1 2\n";
cout<<"1 4\n";
cout<<"1 5\n";
cout<<"1 6\n";
cout<<"1 7\n";
cout<<"3 4\n";
continue;
}
if(n&1){
cout<<((n+1)>>1)<<' '<<((n+1)>>1)+1<<'\n';
cout<<"2 4\n";
for(int i=6;i<=n;i+=2) cout<<"1 "<<i<<'\n';
for(int i=3;i<=n;i+=2) cout<<"2 "<<i<<'\n';
continue;
}
}
return 0;
}
```