题目大意
题目描述
给定一棵包含 n 个节点的无根树。
Cyndaquil 起初位于一个非叶子节点 v。在每一个回合中，他可以选择停留在当前节点，或者移动到相邻的一个节点。他的目标是到达树的任意一个叶子节点（度数为 1 的节点）。
Snorlax 试图阻止他到达叶子节点。Snorlax 可以选择在一条边上睡觉，此时 Cyndaquil 将无法通过这条边。同一时刻最多只有一条边会被阻塞（即只有最新选择的边会被阻塞）。
Snorlax 移动有冷却时间。初始时冷却时间为 0。当冷却时间 ≤0 时，Snorlax 可以选择一条新的边进行阻塞（他也可以选择暂不行动）。一旦他移动并选择了一条新边，冷却时间就会重置为 k。
在 Cyndaquil 的每个回合之后（即使他选择停留），Snorlax 的冷却时间都会减少 1。
两人轮流行动，Snorlax 先手，且初始时没有任何边被阻塞。假设双方都采取最优策略，判断 Cyndaquil 是否一定能在有限的回合内到达某个叶子节点。
输入格式
第一行包含一个整数 t (1≤t≤104)，表示测试用例的数量。
每个测试用例的第一行包含三个整数 n、k 和 v (3≤n≤5⋅105，1≤k,v≤n)，分别表示树的节点数、Snorlax 的冷却时间以及 Cyndaquil 的初始起点。
接下来 n−1 行，每行包含两个整数 a 和 b (1≤a,b≤n，a=b)，表示树上连接节点 a 和 b 的一条边。
保证给定的图是一棵树，且起点 v 不是叶子节点。所有测试用例的 n 之和不超过 5⋅105。
输出格式
对于每个测试用例，输出一行 “YES” 或 “NO”（大小写不敏感），表示 Cyndaquil 是否一定能在有限回合内到达叶子节点。
样例输入
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
| 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
|
样例输出
样例解释
在第一个测试用例中：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 找一个无弦环）（这种题目，我感觉啊，想要做出来的话，要么就是你的思路得比较好，要么就是还是得写个对拍）
这道题目有一个地方还是很难想到的，需要写一个对拍。
在写一个暴力程序之前（当然，特别暴力的除外啊，特别暴力的就不用想了，但是不是所有的题目都可以非常轻松的找到一个特别暴力的写法，特别是这种博弈题目），一定要想清楚这个状态转移图像。
我们不难得到这样的图像：
然后，我们来想如何具体实现，这种样子，我们非常容易想到这个记忆化 dfs。但是，有环的话，不能够使用记忆化 dfs，毕竟记忆化 dfs 就是 dp，只能够在 DAG 上使用。
于是我们想到记忆化 bfs。但是一次正向的记忆化 bfs 很难实现类似的这种可以计算前驱后驱的这个复杂运算。
但是一次不行，就跑两次呗。我们可以跑一次正向 bfs，记住这个出去的红色节点数量（即红色出度）和出去的这个蓝色节点数量（即蓝色出度）。（你也可以理解这次 bfs 就是在把这张反图建出来，毕竟不把图建出来，很难进行这个反向 bfs）然后再跑一次这个反向 bfs，从所有合法点一路往上推，通过减去红色计数器和蓝色计数器，实现类似于或的效果，把红色计数器和蓝色计数器并起来，实现红蓝 and 的效果。
当然我们也不知道对不对，试一试吧。
试过了，上面👆这种做法很难写对，也不是错吧，很难写对。我们不妨啊，一轮，拆成两个操作来看，这样可以避免红蓝之间转移的尴尬问题。
一定要把这个状态转移图设计为红蓝互不相交的情况，至少要把逃跑者选择和阻塞者选择分开。
好的暴力果然是非常优美啊，一次写对。
采用了朴素的，不动点式的更新方法：
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
| 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;
}
}
}
}
}
|
暴力程序
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
|
#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;
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);
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。
其实像上面👆这么想，有一个非常阴的地方，就是，阻塞者是动态的，且可以不操作的，阻塞者可能不急于操作，而是看你怎么操作以后，他再出手，逼你从优势位置移动出来。这么讲很抽象是吧？我们直接拿对拍出来的样例来说。
1
2
3
4
5
6
7
8
9
| 1
7 2 1
1 2
1 3
2 4
1 5
5 6
3 7
|
这个样例应该输出 no，原因和上面说的一样。阻塞者可能不急于操作，而是看你怎么操作以后，他再出手，逼你从优势位置移动出来。
所以说要怎么解决这个问题呢？还是挺难的。
像这种博弈题目，一定要想到的就是两者的最优策略是什么？一定要想两者的最优策略是什么。
Snorlax 试图阻止 Cyndaquil 到达叶子节点，他的最优策略是在 Cyndaquil 即将到达叶子节点（或必胜节点）前的最后一步进行封锁。我们其实已经通过对拍呀，通过什么方式找到了这个比较特殊的这个例子。但是我们没有总结出来，就是阻塞者他的这个策略是什么，就这种博弈题目一定要去想他们的最优策略是什么。
因此，其实我们就是看这个拉扯距离。
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
| 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";
|
AC代码
AC
https://codeforces.com/contest/2207/submission/366188285
源代码
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
#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;
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;
}
|
心路历程（WA，TLE，MLE……）
