B. Beginner's Zelda 题解

题意简述

给定一棵树。

一次操作可以选择两个顶点 $u$ 和 $v$，然后把路径 $u \to v$ 上的所有顶点压缩成一个新顶点。路径上的原顶点都会被删除，所有原本和这条路径上某个点相连的边，都会改为连向这个新顶点。

要求最少进行多少次操作，才能让整棵树最后只剩下一个顶点。

核心结论

设一棵树的叶子结点个数为 $K$，那么答案为：

$$\left\lceil \frac{K}{2} \right\rceil$$

由于标程输出的是：

$$\frac{K+1}{2}$$

这里是整除写法，所以它等价于：

$$\left\lceil \frac{K}{2} \right\rceil$$

因此，这道题的本质就是：

• 统计整棵树有多少个叶子结点；
• 输出 $\left\lceil \dfrac{K}{2} \right\rceil$。

为什么答案只和叶子数有关

树中最难被“合并掉”的部分其实是叶子。

一次操作选择一条路径并压缩后，路径两端如果是两个叶子，那么这两个叶子会一起消失。也就是说，一次操作最多可以有效消掉 $2$ 个叶子。

因此如果一棵树有 $K$ 个叶子，那么无论如何，答案都不可能小于：

$$\left\lceil \frac{K}{2} \right\rceil$$

这给出了一个下界。

接下来只要证明这个下界一定能够达到，就说明答案就是它。

正确性证明

我们用归纳法证明：任意一棵有 $K$ 个叶子的树，最少操作次数一定是

$$\left\lceil \frac{K}{2} \right\rceil$$

基础情况

当叶子数 $K=2$ 时，树一定是一条链。

这时直接选择这条链的两个端点作为 $u,v$，一次操作就能把整棵树压成一个点，所以答案是：

$$1=\left\lceil \frac{2}{2} \right\rceil$$

当叶子数 $K=3$ 时，显然至少需要 $2$ 次操作，而这个值也可以达到，因此答案是：

$$2=\left\lceil \frac{3}{2} \right\rceil$$

归纳步骤

现在考虑叶子数更多的情况。

关键观察是：

当树的叶子数不少于 $4$ 时，一定可以找到两个叶子，使得把它们之间的路径压缩后，新生成的点不是叶子，也就是它的度数大于 $1$。

为什么这个结论成立？

• 如果树中存在至少两个度数不小于 $3$ 的点，那么一定可以选到两个叶子，使得这两个高分叉点都位于它们的路径上。这样压缩后，新点会同时接出多个分支，所以不会是叶子。
• 如果不存在两个这样的点，那么树中一定有某个点的度数至少为 $4$。此时选取来自不同分支的两个叶子，它们路径经过这个点，压缩后新点同样至少连向另外两个分支，因此也不会成为叶子。

于是，我们可以在一次操作中做到：

• 删去 $2$ 个叶子；
• 新产生的点不是叶子，因此叶子总数恰好减少 $2$。

也就是说，一次操作后，叶子数从 $K$ 变成了：

$$K-2$$

根据归纳假设，把剩下的树缩成一个点还需要：

$$\left\lceil \frac{K-2}{2} \right\rceil$$

次操作，因此总操作次数为：

$$1+\left\lceil \frac{K-2}{2} \right\rceil = \left\lceil \frac{K}{2} \right\rceil $$

于是结论成立。

所以最终答案就是：

$$\left\lceil \frac{K}{2} \right\rceil$$

标程为什么这样写

标程的核心代码是：

for (int i = 1, a, b; i < n; i++) {
  cin >> a >> b;
  freq[a]++;
  freq[b]++;
}
int cnt = 0;
for (int i = 1; i <= n; i++)
  cnt += (freq[i] == 1),
  freq[i] = 0;
cout << (cnt + 1) / 2 << '\n';

其中：

• freq[i] 统计的是结点 $i$ 的度数；
• 在树中，度数等于 $1$ 的点就是叶子；
• cnt 就是叶子个数 $K$；
• 输出 (cnt + 1) / 2，也就是：

$$\left\lceil \frac{K}{2} \right\rceil$$

所以整份代码的逻辑非常直接：

1. 读入整棵树；
2. 统计每个点的度数；
3. 数一数有多少个度数为 $1$ 的点；
4. 输出 $\left\lceil \dfrac{K}{2} \right\rceil$。

复杂度分析

对于每组测试数据，只需要遍历所有边和所有点各一次，因此时间复杂度为：

$$O(n)$$

空间复杂度为：

$$O(n)$$

由于所有测试数据的 $n$ 之和不超过 $10^5$，所以这样做完全可以通过。

参考代码

#include <cmath> 
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <cstring>
#include <numeric>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 1e6 + 5;
const int inf = 1e9 + 5;
int n, k, m, q;
int freq[nmax];

static void testcase() {
  cin >> n;
  for (int i = 1, a, b; i < n; i++) {
    cin >> a >> b;
    freq[a]++;
    freq[b]++;
  }
  int cnt = 0;
  for(int i = 1; i <= n; i++)
    cnt += (freq[i] == 1),
    freq[i] = 0;
  cout << (cnt + 1) / 2 << '\n';
  return;
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  for (int i = 0; i < t; i++)
    testcase();
}