自动搬运

查看原文

来自洛谷，原作者为

	Danno0v0 我们会再次见面的，相信我。再见。

搬运于2025-08-24 22:34:07，当前版本为作者最后更新于2021-10-18 20:49:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Update on 10/24

修改了后半篇一部分错误的口胡。

一道大大大水题。

首先题上说，重心是唯一的。

这太好办了，菊花图。

那么，我们再看：直径重心唯一。

那么可以想到直径长度应该是个奇数。

咦，直径重心不能等于树的重心？

熟悉图论题里特（ du ）殊（ liu ）图的同学可能已经想到了这是什么了。

把菊花图稍加改造，那么就可以请出我们的——蒲公英。

对了，因为直径重心唯一，所以直径长度不能为偶数——还有不能大于节点数一半，别让重心偏移。

最后来看，唔嗯，直径要唯一。

原来的菊花图中每一条边和这个长长的链都构成了直径。

那么我们把原来菊花图中一条边延长一个节点，这样它和这个长长的链接在一起就是唯一的直径啦，因为其余的边如果与那条链接在一起总会比直径长度小 $1$ 。

就像这样：

那么，我们总结一下。

我们的基础是一个蒲公英。

然后这条蒲公英上的链的节点个数不大于节点总数一半。

然后我们需要在另外一条边上接上一个节点，保证直径唯一。

最后保证直径的重心（也就是中间那个）不是树的重心。

那么，根据这些，我们就可以造出究极完全态兜心の顶之树（根据上面这些条件，造出的树可能不唯一，我是这样造的）——

$3$ 号节点为重心， $1$ 号与 $2$ 号一起保证直径唯一， $4567$ 是蒲公英的链，长度为 $7$ 的直径可以保证树的重心不与直径重心重合。

然后 $8$ 及 $8$ 以后的节点皆可以直接接到 $3$ 号节点上，可以动手画一下，完全不破坏这棵树的性质（就像那些节点，更多的节点，还是更多的节点一样）。

而当节点数小等于于 $8$ 的时候可以证明（我是全画了一遍 orz ：要么会成为菊花图，要么就只有一条链，要么直径长度不为奇数，要么重心会偏到链上去，要么是树的重心有两个），没有办法造出来，所以输出 $-1$ 就完咯。

然后就做完了，真是一道大大大水题。

code：

对于这种大水题压一下行不过分吧以及挑战全网最简洁代码： $7$ 行

#include<bits/stdc++.h>
int main(){
	int n;
	std::cin>>n;
	if(n<=8)std::cout<<-1;
	else{std::printf("%d\n%d %d\n%d %d\n%d %d\n%d %d\n%d %d\n%d %d\n",n,1,2,2,3,3,4,4,5,5,6,6,7);
	for(int j=8;j<=n;j++){std::printf("%d %d\n",3,j);}}}