[EC Final 2022] Chase Game 2

形式化题目

给定一棵 $n$ 个点的树。Pang 与 Shou 在树上玩追逃游戏：Shou 先走，每回合两人各自选择「留在原地」或「走到相邻点」，两人同处一点时 Shou 被抓住。Pang 想在有穷回合内抓住 Shou。

现在允许添加若干条边（树变成一般连通图），使得对任意初始位置对 $(u,v)$ ，Pang 都无法在有穷回合内抓住 Shou。求最少添加的边数；若不存在这样的加边方案，输出 $-1$ 。

正解

思路

1. 什么样的局面 Pang 必胜？

树的直径、度数结构决定了追逃结果。关键观察：Pang 的必胜局面只会是「Shou 在一个叶子 $b$ 、Pang 在 $b$ 的父亲 $p$ 」——此时 Shou 无处可逃，只能原地或走向 $p$ ，两条路都被堵死。

因此要让 Pang 对所有初始位置都无必胜策略，就必须让每个叶子 $b$ 在被追到「 $b+p$ 」时仍有出路：即每个叶子都要新增一条边，连到一个不是它父亲的点上。

2. 为什么同组叶子之间连边无效？

设叶子 $b_1, b_2$ 的父亲都是 $p$ 。若新增边 $(b_1,b_2)$ ：Shou 在 $b_1$ 、Pang 在 $p$ 时跳到 $b_2$ ，但下一回合 Pang 从 $p$ 走到 $b_2$ 就抓住了（ $b_2$ 的邻居只有 $p$ 和 $b_1$ ，而 $b_1$ 也是 Patty 一步可达）。

所以按叶子的父亲分组，同一组内的叶子之间连边救不了它们，新边必须跨组（或连向非父亲的内部点）。

3. 下界与构造

设叶子总数 $L$ ，按父亲分组后最大组大小为 $M$ 。每条新边有两个端点，最多能「覆盖」两个叶子（把它的两端都变成安全点），所以至少需要 $\lceil L/2\rceil$ 条边；又因同组叶子不能互相连，最大组 $M$ 个叶子各自都需要一条通往组外的边，所以至少 $M$ 条。

两个下界可同时取到（把不同组的叶子两两配对连边，组内多余的叶子连向任意非父亲点），故

\text{答案}=\max\left(\left\lceil \frac{L}{2}\right\rceil,\; M\right)

4. 菊花图无解

若树是菊花图（ $n-1$ 个叶子共用一个中心），则任何两片叶子之间加边，Pang 都能从中心一步到达；叶子连向中心无用。故无论如何加边都存在被抓住的初始局面，输出 $-1$ （ $n\le 3$ 的树都是菊花图，一并覆盖）。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 15:23
 * update_at: 2026-10-02 15:23
 *
 * P9725 [EC Final 2022] Chase Game 2
 * 一棵树，Shou 先走，Pang 来追。问最少加多少条边，才能让 Pang 永远抓不到 Shou。
 * 结论：Pang 的必胜点只会出现在“叶子 b + b 的父亲 p”这种局面上，
 *       所以每个叶子必须至少连出去一条“指向非 p 邻点”的新边。
 *       叶子按父亲分组，同组叶子之间连边无效，答案 = max(ceil(L/2), 最大组大小)；
 *       菊花图（含 n<=3）无解，输出 -1。
 */
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 1e5+5;

int n;
int deg[maxn];          // deg[x]：点 x 的度数
int leaf_cnt[maxn];     // leaf_cnt[x]：x 的邻点中有多少个叶子
int eu[maxn], ev[maxn]; // 把树边存下来，后面统计叶子要用

void read_data(){
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; ++i) { // 多测清空
            deg[i] = 0;
            leaf_cnt[i] = 0;
        }
        for (int i = 1; i < n; ++i) {
            int u, v;
            cin >> u >> v;
            eu[i] = u;
            ev[i] = v;
            deg[u]++;
            deg[v]++;
        }

        int maxdeg = 0;
        for (int i = 1; i <= n; ++i) {
            maxdeg = max(maxdeg, deg[i]);
        }
        // 菊花图：所有叶子共用一个父亲，加任何叶子之间的边都会被那个父亲一步吃掉；
        // n<=2 与 n=3 的树也正好是菊花图，一并判掉。
        if (maxdeg == n - 1) {
            cout << -1 << "\n";
            continue;
        }

        // 统计叶子总数 L，以及每个点名下有 t[i] 个叶子儿子
        int L = 0;
        for (int i = 1; i < n; ++i) {
            if (deg[eu[i]] == 1) {
                leaf_cnt[ev[i]]++;
                L++;
            }
            if (deg[ev[i]] == 1) {
                leaf_cnt[eu[i]]++;
                L++;
            }
        }

        int maxGroup = 0;
        for (int i = 1; i <= n; ++i) {
            maxGroup = max(maxGroup, leaf_cnt[i]);
        }

        // 每条新边最多救两个叶子 -> 至少 ceil(L/2) 条；
        // 同一组的叶子之间不能连 -> 最大组里的每个叶子都要单独用一条边 -> 至少 maxGroup 条。
        int ans = max((L + 1) / 2, maxGroup);
        cout << ans << "\n";
    }
}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    read_data();
    
    return 0;
}

复杂度

时间复杂度： $O(n)$ 每个测试用例（只统计度数、叶子数与分组最大值）。
空间复杂度： $O(n)$ 。

总结

树上追逃的必胜局面是局部形态（叶子 + 其父），把全局问题化归为「每个叶子都要有额外出路」。
答案由两个下界取 max：配对下界 $\lceil L/2\rceil$ 与同组冲突下界 $M$ 。
菊花图是唯一无解形态——加边无法让叶子摆脱中心的一步威胁。