自动搬运

查看原文

来自洛谷，原作者为

	Leasier 我们所知的是沧海一粟，我们所不知的是汪洋大海。

搬运于2025-08-24 22:02:26，当前版本为作者最后更新于2022-10-28 00:07:25，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意可以转化为：在一棵树上加尽量少的边，使得每条边至少在一个环中。

首先不难通过样例发现下面两个结论：

• Observation 1. $k = \lceil \frac{leaf}{2} \rceil$，其中 $leaf$ 表示叶子数。
• Observation 2. 最优方案中的所有 $a, b$ 一定均为叶子。

Observation 2 的证明：

我们显然可以将加一条边 $(u, v)$ 等效为：

• 让树上 $u, v$ 这条链上的所有边达成“至少在一个环中”的目标。

于是（下文假定我们随意钦定一个点为根且 $a$ 的深度小于 $b$）：

1. $a$ 为 $b$ 的祖先

首先，由于 $n \geq 3$，原树中不可能仅仅存在 $1$ 个叶子。

于是此时我们将 $b$ 替换为一个 $b$ 子树内的叶子、将 $a$ 替换为一个叶子 $a'$ 使得 $lca(a', b)$ 为 $a$ 的祖先。

2. $a$ 不为 $b$ 的祖先

此时可以达成目标的最浅点固定为 $lca(a, b)$。

于是我们把 $a, b$ 分别替换为其子树内的一个叶子即可。

Observation 1 的证明：

首先这玩意显然是答案下界——因为我们会尽量不重复地选叶子。

然后就是人类智慧的一步了——

• 我们把所有叶子抓出来，按 dfs 序升序排序，前一半与后一半的对应点配对，如果最后单出一个最大的就跟最小的配对。

那它为什么是对的？我们考虑一个非根节点 $u$。

1. $u$ 子树内叶子个数 $\leq \lfloor \frac{leaf}{2} \rfloor$

此时 $u \to fa_u$ 一定会达成目标，因为一定有从内向外的连边。

2. $u$ 子树内叶子个数 $> \lfloor \frac{leaf}{2} \rfloor$

显然此时 $u$ 子树内不会涵盖所有叶子，于是最小 / 最大之一总会向其中连边。

至此 Observation 1 得证。然后这道题就做完了。

代码：

#include <stdio.h>

typedef struct {
	int nxt;
	int end;
} Edge;

int cnt = 0;
int head[500007], deg[500007], rnk[500007], leaf[500007];
Edge edge[1000007];

inline void add_edge(int start, int end){
	cnt++;
	edge[cnt].nxt = head[start];
	head[start] = cnt;
	edge[cnt].end = end;
}

void dfs(int u, int father, int &id){
	rnk[++id] = u;
	for (int i = head[u]; i != 0; i = edge[i].nxt){
		int x = edge[i].end;
		if (x != father) dfs(x, u, id);
	}
}

int main(){
	int n, id = 0, leaf_cnt = 0, half;
	scanf("%d", &n);
	for (int i = 1; i < n; i++){
		int a, b;
		scanf("%d %d", &a, &b);
		deg[a]++;
		deg[b]++;
		add_edge(a, b);
		add_edge(b, a);
	}
	dfs(1, 0, id);
	for (int i = 1; i <= n; i++){
		if (deg[rnk[i]] == 1) leaf[++leaf_cnt] = rnk[i];
	}
	half = leaf_cnt / 2;
	printf("%d\n", (leaf_cnt + 1) / 2);
	for (int i = 1; i <= half; i++){
		printf("%d %d\n", leaf[i], leaf[i + half]);
	}
	if (leaf_cnt % 2 != 0) printf("%d %d", leaf[1], leaf[leaf_cnt]);
	return 0;
}