「CEOI2017」Mousetrap

#题面

#题目描述

有一个有 $n$ 个房间和 $n-1$ 条走廊的迷宫，保证任意两个房间可以通过走廊互相到达，换句话说，这个迷宫的结构是一棵树。

一个老鼠被放进了迷宫，迷宫的管理者决定和老鼠做个游戏。

一开始，有一个房间被放置了陷阱，老鼠出现在另一个房间。老鼠可以通过走廊到达别的房间，但是会弄脏它经过的走廊。老鼠不愿意通过脏的走廊。

每个时刻，管理者可以进行一次操作：堵住一条走廊使得老鼠不能通过，或者擦干净一条走廊使得老鼠可以通过。然后老鼠会通过一条干净的并且没被堵住的走廊到达另一个房间。只有在没有这样的走廊的情况下，老鼠才不会动。一开始所有走廊都是干净的。管理者不能疏通已经被堵住的走廊。

现在管理者希望通过尽量少的操作将老鼠赶到有陷阱的房间，而老鼠则希望管理者的操作数尽量多。请计算双方都采取最优策略的情况下管理者需要的操作数量。

注意：管理者可以选择在一些时刻不操作。

#输入格式

第一行三个空格隔开的正整数数 $n,t,m$。分别代表房间的个数，陷阱房的编号和老鼠起始房间的编号。

接下来 $n-1$ 行，每行两个空格隔开的整数 $a_i,b_i$，表示有一条走廊连接编号为 $a_i$ 和 $b_i$ 的房间。

#输出格式

输出一行包含一个整数，表示双方都采取最优策略的情况下，管理者需要的操作数量。

#输入输出样例

样例输入 #1

10 1 4
1 2
2 3
2 4
3 9
3 5
4 7
4 6
6 8
7 10

样例输出 #1

4

样例解释 #1

• 管理者先堵住房间 $4$ 和 $7$ 之间的走廊。
• 老鼠走到房间 $6$。房间 $4$ 和 $6$ 之间的走廊现在是脏的。
• 管理者堵住房间 $6$ 和 $8$ 之间的走廊。
• 老鼠不能动。
• 管理者清理房间 $4$ 和 $6$ 之间的走廊，房间 $4$ 和 $6$ 之间的走廊现在是干净的。
• 老鼠走到房间 $4$，房间 $4$ 和 $6$ 之间的走廊现在是脏的。
• 管理者堵住房间 $2$ 和 $3$ 之间的走廊。
• 老鼠走到房间 $2$，房间 $2$ 和 $4$之间的走廊现在是脏的。
• 管理者不进行操作。
• 老鼠走到房间 $1$。

这个过程中管理者总共进行了 $4$ 次操作。

#数据范围与约定

• 子任务 1（$20\%$）: $1 \le n \le 10$；
• 子任务 2（$25\%$）: $1 \le n \le 10^6$，保证老鼠的起始位置和陷阱房相邻；
• 子任务 3（$20\%$）: $1 \le n \le 1000$；
• 子任务 4（$35\%$）: $1 \le n \le 10^6$。

#思路

昨天上课讲的这道题。

从老鼠的位置开始考虑没有什么好的想法，于是从陷阱房的位置开始考虑。由题可知这个迷宫的形态是一棵树，那么设陷阱房为树根。

先来考虑一种特殊情况：老鼠的起始房间与陷阱房相邻。此时老鼠一定会向下面最深的子树走。那么先堵住通向最深的子树的走廊，那么老鼠就会走向次深的子树，显然这样可以减少操作数量。当老鼠被困在某个叶子节点后，将从该叶子节点通向根节点的路径上的通向其他子树的走廊都堵住，再擦干净这条路径即可使老鼠走入陷阱房。

考虑树形 DP，设 $f_x$ 为老鼠在点 $x$ 进入 $x$ 的子树后，将其又赶回点 $x$ 的最小操作次数，得：

$$\tag{1} f_x = \underset{y \in \text{son}(x)}{\text{2nd-max}}\{f_y\} + |\text{son}(x)|$$

其中 $\text{2nd-max}$ 表示次大值。$|\text{son}(u)|$ 表示 $x$ 的子树个数。

下面再来考虑一般情况：老鼠的起始房间与陷阱房不相邻。此时，一开始老鼠不一定会直接向下走，它可以先向上跳，到达某个节点后再开始向下走，开始走后老鼠对走哪个儿子的选择取决于管理者堵边的情况。向下走的时候转移方程同 $(1)$。对于向上走的情况可以二分处理。

求出 $g_x$ 表示根节点到 $x$ 的路径中所有分叉路数量：

$$g_x = \begin{cases} 0 & (x = t) \\ g_{\mathit{fa}} + |\text{son}(x)| - 1 & (x = m) \\ g_{\mathit{fa}} + |\text{son}(x)| - 2 & (\text{otherwise}) \\ \end{cases}$$

设 $t \to m$ 的路径上结点集合为 $S$，对于路径上每一个点 $x$ 的分叉子树结点考虑，如果其满足下列条件之一，则需要堵住通往这条分叉子树的边：

1. $v \in \text{son}(x), v \not \in S$；
2. $g_u + f_v > \mathit{mid}$。

如果满足以下条件，则 $\mathit{mid}$ 不合法：

• 经过 $\mathit{mid}$ 次操作后无法堵住所有需要堵住的边；
• 当老鼠走到 $u$ 处时，但 $u$ 处需要被堵住的通往分叉子树的边没有被堵住。

二分完成后输出答案即可。

#代码

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
87
88
89
90
91

#include <iostream>
#include <vector>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 1e6 + 5;

int n, t, m, fa[N], sum[N], f[N], ans;
bool vis[N];
std::vector<int> g[N];

void dfs(int u, int _f) {
    int max1 = 0, max2 = 0;

    fa[u] = _f;

    if (u != t) {
        sum[u] = sum[_f] + g[u].size() - 1 - (u != m);
    }

    for (const int &v : g[u]) {
        if (v == _f) continue;

        dfs(v, u);

        if (f[v] > max1) {
            max2 = max1;
            max1 = f[v];
        } else if (f[v] > max2) {
            max2 = f[v];
        }
    }

    f[u] = max2 + g[u].size() - 1;
}

bool check(int x) {
    for (int i = m, cnt = 1; i != t; i = fa[i], cnt++) {
        int t = 0;

        for (const int &v : g[i]) {
            if (vis[v] || sum[i] + f[v] <= x) continue;
            if (!cnt) return false;

            t++, cnt--;
        }

        x -= t;
    }

    return x >= 0;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> t >> m;

    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(t, 0);

    for (int i = m; i; i = fa[i]) {
        vis[i] = true;
    }

    int l = 0, r = n << 1;

    while (l <= r) {
        int mid = l + r >> 1;

        if (check(mid)) {
            r = mid - 1;
            ans = mid;
        } else {
            l = mid + 1;
        }
    }

    cout << ans << endl;

    return 0;
}