【题解】P7903 「DCOI」兜心の顶

出题人题解。

C 兜心の顶

按道理边做这题边点开 P7238、P7807，应该通过率 100% 吧。

下文中「唯一性」代指直径、重心、直径重心三个「唯一」，「不等性」代指树的重心不等于直径重心。

一、直径的长度讨论

首先直径 不会是偶数。

否则设直径的长度是 \(2k\)，由 \(1\cdots 2k\) 这 \(2k\) 个结点组成。

那么结点 \(k\) 和结点 \(k+1\) 必然都是直径重心，与唯一性不符，舍去。

然后直径不可能是 \(1\)：显然。

直径不可能是 \(3,5\)：此时重心只能出现在中间的点（否则与唯一性不符），与不等性不符。

综上，直径长度至少为 \(7\) 且必为奇数。

二、重心位置的讨论

不妨钦定我们构造的树的直径就是 \(7\)，下面来看看位置：

首先直径的重心一定是 \(1\cdots7\) 号结点的中点：\(4\) 号结点。

那么树的重心一定要出现在其他结点上，首先 \(1,2,6,7\) 被排除，理由是唯一性。

那么只剩下 \(3,5\) 两个对称的结点，我们不妨设重心是 \(3\) 号结点。

此时需要给 \(3\) 号结点再安排上一些子树，为了不影响唯一性，\(3\) 的其他子树深度只能为 \(1\)。

那么考虑到 \(3\) 必须是唯一重心，至少要加入两个新结点，才能保证。

综上，树的大小至少为 \(9\)，且形态为：

其中 \(\color{red}3\) 是树的重心，\(\color{blue}4\) 是直径重心，上面的这一条链就是直径。

三、N >= 10 情况的讨论

不难发现，只要我们继续按照该策略，不断地给结点 \(3\) 添加新的子结点（形成一张菊花图）即可。

四、代码实现

当 \(N\le8\) 时：输出 -1。

其他情况，先输出

这个基本模型，然后对于 \(i=8\sim N\) 的所有结点 \(i\)，全部连向结点 \(3\) 即可。

std

#include<cstdio>
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
int print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
	return 0;
}
int main(){
	int n = init();
	if (n <= 8) return print(-1);
	print(n), putchar('\n');
	for (int i = 1; i <= 6; ++i)
		print(i), putchar(' '), print(i+1), putchar('\n');
	for (int i = 8; i <= n; ++i)
		print(3), putchar(' '), print(i), putchar('\n');
}

五、后记

本题显然有很多合理的构造，但是我发现本构造最为清晰、整洁、易懂。