Skip to content

「CEOI2017」Mousetrap

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

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

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

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

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

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

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

#输入格式

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

接下来 n1n-1 行,每行两个空格隔开的整数 ai,bia_i,b_i,表示有一条走廊连接编号为 aia_ibib_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

  • 管理者先堵住房间 4477 之间的走廊。
  • 老鼠走到房间 66。房间 4466 之间的走廊现在是脏的。
  • 管理者堵住房间 6688 之间的走廊。
  • 老鼠不能动。
  • 管理者清理房间 4466 之间的走廊,房间 4466 之间的走廊现在是干净的。
  • 老鼠走到房间 44,房间 4466 之间的走廊现在是脏的。
  • 管理者堵住房间 2233 之间的走廊。
  • 老鼠走到房间 22,房间 2244之间的走廊现在是脏的。
  • 管理者不进行操作。
  • 老鼠走到房间 11

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

#数据范围与约定

  • 子任务 1(20%20\%): 1n101 \le n \le 10
  • 子任务 2(25%25\%): 1n1061 \le n \le 10^6,保证老鼠的起始位置和陷阱房相邻;
  • 子任务 3(20%20\%): 1n10001 \le n \le 1000
  • 子任务 4(35%35\%): 1n1061 \le n \le 10^6

#思路

昨天上课讲的这道题。

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

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

考虑树形 DP,设 fxf_x 为老鼠在点 xx 进入 xx 的子树后,将其又赶回点 xx 的最小操作次数,得:

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

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

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

求出 gxg_x 表示根节点到 xx 的路径中所有分叉路数量:

gx={0(x=t)gfa+son(x)1(x=m)gfa+son(x)2(otherwise)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}

tmt \to m 的路径上结点集合为 SS,对于路径上每一个点 xx 的分叉子树结点考虑,如果其满足下列条件之一,则需要堵住通往这条分叉子树的边:

  1. vson(x),v∉Sv \in \text{son}(x), v \not \in S
  2. gu+fv>midg_u + f_v > \mathit{mid}

如果满足以下条件,则 mid\mathit{mid} 不合法:

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

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

#代码

C++
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;
}