Codeforces Round 1085 (Div. 1 + Div. 2)——CF-2207-D. Boxed Like a Fish（阻塞者阻止移动者前往叶子节点）（暴力程序 bfs 的书写，最重要的还是和做题的一样的，用什么代表一个状态）（有环的话，不能够使用记忆化 dfs，毕竟记忆化 dfs 就是 dp，只能够在 DAG 上使用）（像这种博弈题目，一定要想到的就是两者的最优策略是什么？一定要想两者的最优策略） · znzryb
## 题目大意
**题目描述**
给定一棵包含 $n$ 个节点的无根树。
Cyndaquil 起初位于一个非叶子节点 $v$。在每一个回合中，他可以选择停留在当前节点，或者移动到相邻的一个节点。他的目标是到达树的任意一个叶子节点（度数为 $1$ 的节点）。
Snorlax 试图阻止他到达叶子节点。Snorlax 可以选择在一条边上睡觉，此时 Cyndaquil 将无法通过这条边。同一时刻最多只有一条边会被阻塞（即只有最新选择的边会被阻塞）。
Snorlax 移动有冷却时间。初始时冷却时间为 $0$。当冷却时间 $\le 0$ 时，Snorlax 可以选择一条新的边进行阻塞（他也可以选择暂不行动）。一旦他移动并选择了一条新边，冷却时间就会重置为 $k$。
在 Cyndaquil 的每个回合之后（即使他选择停留），Snorlax 的冷却时间都会减少 $1$。
两人轮流行动，Snorlax 先手，且初始时没有任何边被阻塞。假设双方都采取最优策略，判断 Cyndaquil 是否一定能在有限的回合内到达某个叶子节点。
**输入格式**
第一行包含一个整数 $t$ ($1 \le t \le 10^4$)，表示测试用例的数量。
每个测试用例的第一行包含三个整数 $n$、$k$ 和 $v$ ($3 \le n \le 5 \cdot 10^5$，$1 \le k, v \le n$)，分别表示树的节点数、Snorlax 的冷却时间以及 Cyndaquil 的初始起点。
接下来 $n-1$ 行，每行包含两个整数 $a$ 和 $b$ ($1 \le a, b \le n$，$a \neq b$)，表示树上连接节点 $a$ 和 $b$ 的一条边。
保证给定的图是一棵树，且起点 $v$ 不是叶子节点。所有测试用例的 $n$ 之和不超过 $5 \cdot 10^5$。
**输出格式**
对于每个测试用例，输出一行 "YES" 或 "NO"（大小写不敏感），表示 Cyndaquil 是否一定能在有限回合内到达叶子节点。
**样例输入**
```
6
6 2 1
1 2
2 3
2 4
1 5
5 6
7 1 4
1 2
2 3
3 4
4 5
5 6
6 7
3 1 3
1 3
2 3
4 1 4
1 3
3 4
4 2
9 3 5
4 5
5 6
4 7
9 8
8 7
1 2
2 3
3 4
9 4 5
4 5
5 6
4 7
9 8
8 7
1 2
2 3
3 4
```
**样例输出**
```
YES
NO
YES
NO
NO
YES
```
**样例解释**
在第一个测试用例中：Cyndaquil 从节点 $1$ 出发。如果 Snorlax 选择阻塞节点 $1$ 到节点 $2$ 的边，那么 Cyndaquil 可以在两个回合后走到叶子节点 $6$。否则，Cyndaquil 可以直接移动到节点 $2$，此时 Snorlax 无法同时阻止他前往叶子节点 $3$ 或 $4$，Cyndaquil 必然能到达其中一个。
在第二个测试用例中：由于冷却时间 $k=1$ 极短，Snorlax 可以频繁移动，可以证明 Snorlax 能够无限期地阻止 Cyndaquil 到达树两端的叶子节点 $1$ 或 $7$。
不难发现样例 2，移动者会被困在 3,4 之间，因为阻塞者冷却时间太快了，只有 1。
样例 5 到达不了叶子节点
## 暴力程序书写指导
**暴力程序 bfs 的书写****，最重要的还是和做题的一样的，****用什么代表一个状态****。**
为什么要书写暴力 bfs 程序？因为以我的这个经验，这种图论题目，你想一遍写对，基本不可能，以类似题目 F 为例：
[2025-沈阳站-区域赛-F. The Bond Beyond Time（友谊天长地久）（如何使用 bfs 找一个无弦环）（这种题目，我感觉啊，想要做出来的话，要么就是你的思路得比较好，要么就是还是得写个对拍）](/2026/02/02/20260202-a7f17ccc)
这道题目有一个地方还是很难想到的，需要写一个对拍。
在写一个暴力程序之前（当然，特别暴力的除外啊，特别暴力的就不用想了，但是不是所有的题目都可以非常轻松的找到一个特别暴力的写法，特别是这种博弈题目），**一定要想清楚这个状态转移图像**。
我们不难得到这样的图像：
然后，我们来想如何具体实现，这种样子，我们非常容易想到这个记忆化 dfs。**但是**，**有环的话，不能够使用记忆化 dfs，毕竟记忆化 dfs 就是 dp，只能够在 DAG 上使用**。
于是我们想到记忆化 bfs。但是**一次**正向的记忆化 bfs 很难实现类似的这种可以计算前驱后驱的这个复杂运算。
但是**一次不行，就跑两次呗**。我们可以跑一次正向 bfs，记住这个出去的红色节点数量（即**红色出度**）和出去的这个蓝色节点数量（即**蓝色出度**）。（**你也可以理解这次 bfs 就是在把****这张反图****建出来，毕竟不把图建出来，很难进行这个反向 bfs**）然后再跑一次这个反向 bfs，从所有合法点一路往上推，通过**减去红色计数器和****蓝色****计数器**，实现类似于或的效果，把红色计数器和蓝色计数器并起来，实现红蓝 and 的效果。
当然我们也不知道对不对，试一试吧。
试过了，**上面👆这种做法很难写对**，也不是错吧，很难写对。我们不妨啊，一轮，拆成两个操作来看，这样可以避免红蓝之间转移的尴尬问题。
一定要把这个状态转移图设计为红蓝互不相交的情况，至少**要把逃跑者选择和阻塞者选择分开**。
好的暴力果然是非常优美啊，一次写对。
采用了朴素的，不动点式的更新方法：
```cpp
bool changed=true;
while (changed) {
changed=false;
for (const auto &[u,vec]:complex_g) {
if (win[u]) continue;
if (u.turn) {
bool all_win=true;
for (auto son:vec) {
if (!win[son]) {
all_win=false;
break;
}
}
win[u]=all_win;
if (all_win) {
changed=true;
}
}else {
for (auto son:vec) {
if (win[son]) {
win[u]=true;
changed=true;
break;
}
}
}
}
}
```
::: 暴力程序
```cpp
/**
* Problem: D. Boxed Like a Fish
* Contest: Codeforces Round 1085 (Div. 1 + Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2207/problem/D
* Created: 2026-03-10 18:04:13
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
struct Pos_cool_ban_turn {
ll pos,cool,ban,turn;
bool operator<(const Pos_cool_ban_turn &o) const {
if (pos!=o.pos) {
return pos<o.pos;
}
if (cool!=o.cool) {
return cool<o.cool;
}
if (ban != o.ban) return ban<o.ban;
return turn < o.turn;
}
};
void Solve() {
ll N,K,S;
cin >> N >> K >> S;
vector<vector<ll>> g(N+2);
vector<pair<ll,ll>> edges(N+2);
vector<char> is_leaf(N+2);
for (int i=1;i<=N-1;++i) {
ll u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
edges[i]={u,v};
}
for (int i=1;i<=N;++i) {
if (SZ(g[i])==1) {
is_leaf[i]=1;
}
}
if (is_leaf[S]) {
cout<<"YES\n";
return;
}
for (int i=1;i<=N;++i) {
g[i].push_back(i);
}
auto is_ban=[&](ll u,ll v,ll ban_id) -> bool {
pair<ll,ll> edge=edges[ban_id];
pair<ll,ll> ch_edge={u,v};
if (edge.first>edge.second) {
swap(edge.first,edge.second);
}
if (ch_edge.first>ch_edge.second) {
swap(ch_edge.first,ch_edge.second);
}
if (edge==ch_edge) {
return true;
}
return false;
};
map<Pos_cool_ban_turn,vector<Pos_cool_ban_turn>> complex_g;
map<Pos_cool_ban_turn,int> win;
Pos_cool_ban_turn start_status={S,0,0,1};
do {
queue<Pos_cool_ban_turn> q;
set<Pos_cool_ban_turn> memo;
auto add_edge_node=[&](Pos_cool_ban_turn u,Pos_cool_ban_turn v) {
complex_g[u].push_back(v);
if (memo.contains(v)) {
return;
}
q.push(v);
memo.insert(v);
};
add_edge_node({0,0,0,0},start_status);
// q.push({S,0,0,1});
// memo.insert({S,0,0,1});
while (!q.empty()) {
auto [pos,cool,ban,turn]=q.front();
auto u=q.front();
q.pop();
if (turn) {
if (cool<=0) {
for (int i=1;i<=N-1;++i) {
Pos_cool_ban_turn to={pos,K,i,0};
add_edge_node(u,to);
}
}
Pos_cool_ban_turn to={pos,cool,ban,0};
add_edge_node(u,to);
}else {
for (auto v:g[pos]) {
if (is_ban(pos,v,ban)) {
continue;
}
Pos_cool_ban_turn to={v,max(0ll,cool-1),ban,1};
add_edge_node(u,to);
}
}
}
}while (false);
for (auto &[u,vec]:complex_g) {
if (is_leaf[u.pos]) {
win[u]=true;
}
}
bool changed=true;
while (changed) {
changed=false;
for (const auto &[u,vec]:complex_g) {
if (win[u]) continue;
if (u.turn) {
bool all_win=true;
for (auto son:vec) {
if (!win[son]) {
all_win=false;
break;
}
}
win[u]=all_win;
if (all_win) {
changed=true;
}
}else {
for (auto son:vec) {
if (win[son]) {
win[u]=true;
changed=true;
break;
}
}
}
}
}
if (win[start_status]) {
cout<<"YES\n";
}else {
cout<<"NO\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
*/
```
:::
## 思路讲解
S 只要符合这个要求，就是 Yes，否则就是 No。
其实像上面👆这么想，有一个非常阴的地方，就是，阻塞者是动态的，且可以不操作的，**阻塞者可能不急于操作，而是看你怎么操作以后，他再出手，逼你从优势位置移动出来**。这么讲很抽象是吧？我们直接拿对拍出来的样例来说。
```cpp
1
7 2 1
1 2
1 3
2 4
1 5
5 6
3 7
```
这个样例应该输出 no，原因和上面说的一样。**阻塞者可能不急于操作，而是看你怎么操作以后，他再出手，逼你从优势位置移动出来**。
所以说要怎么解决这个问题呢？还是挺难的。
**像这种博弈题目，一定要想到的就是两者的最优策略是什么？一定要想两者的最优策略是什么。**
Snorlax 试图阻止 Cyndaquil 到达叶子节点，他的最优策略是在 Cyndaquil **即将到达叶子节点（或必胜节点）前的最后一步进行封锁**。我们其实已经通过对拍呀，通过什么方式找到了这个比较特殊的这个例子。但是我们没有总结出来，就是阻塞者他的这个策略是什么，就这种博弈题目一定要去想他们的**最优策略是什么**。
因此，其实我们就是看这个**拉扯距离**。
```cpp
auto dfs=[&](auto && go,ll u,ll fa) -> void {
if (SZ(g[u])==1) {
return;
}
vector<ll> rec;
ll lans=INF;
for (auto to:g[u]) {
if (to==fa) {
continue;
}
go(go,to,u);
rec.push_back(dp[to]);
lans=min(dp[to]+1,lans);
}
sort(all(rec));
if (SZ(rec)>=2) {
// rec[0]+rec[1]+2 是拉扯距离总长度
// -1 是因为这个在最后一刻他卡你一下，你需要跑的距离就是总拉扯距离 -1
if (rec[0]+rec[1]+2-1<=K) {
lans=0;
}
}
dp[u]=lans;
};
dfs(dfs,S,-1);
if (dp[S]==0) {
cout<<"YES\n";
return;
}
cout<<"NO\n";
```
## AC代码
AC
[https://codeforces.com/contest/2207/submission/366188285](https://codeforces.com/contest/2207/submission/366188285)
::: 源代码
```cpp
/**
* Problem: D. Boxed Like a Fish
* Contest: Codeforces Round 1085 (Div. 1 + Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2207/problem/D
* Created: 2026-03-11 11:44:05
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
void Solve() {
ll N,K,S;
cin >> N >> K >> S;
vector<vector<ll>> g(N+2);
for (int i=1;i<=N-1;++i) {
ll u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
if (SZ(g[S])==1) {
cout<<"YES\n";
return;
}
vector<ll> dp(N+2);
auto dfs=[&](auto && go,ll u,ll fa) -> void {
if (SZ(g[u])==1) {
return;
}
vector<ll> rec;
ll lans=INF;
for (auto to:g[u]) {
if (to==fa) {
continue;
}
go(go,to,u);
rec.push_back(dp[to]);
lans=min(dp[to]+1,lans);
}
sort(all(rec));
if (SZ(rec)>=2) {
if (rec[0]+rec[1]+2-1<=K) {
lans=0;
}
}
dp[u]=lans;
};
dfs(dfs,S,-1);
if (dp[S]==0) {
cout<<"YES\n";
return;
}
cout<<"NO\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2207/submission/366188285
*/
```
:::
## 心路历程（WA，TLE，MLE……）