#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
const int N = 1e6 + 16;
int n, t, m;
vector<int> g[N];
bool checksubtask2() { // It is guaranteed that a passage between rooms m and t exists.
for (int v : g[m])
if (v == t) return true;
return false;
}
namespace subtask2 {
int dfs(int u, int p) {
if (g[u].size() == 1) return 0; // hết đường
if (g[u].size() == 2) return 1; // còn 1 đường nhưng sẽ bị chặn
vector<int> res;
for (int v : g[u]) if (v != p) {
res.push_back(dfs(v, u) + 1); // nếu chuột chạy vào v thì min bước là ? (+1 lượt dọn phân khi quay lại)
}
sort(all(res), greater<int>());
return g[u].size() - 2 + res[1]; // chặn đường thứ nhất, chuột đi vào đường thứ nhì
}
void solve() {
cout << dfs(m, t) << '\n';
}
}
namespace subtask4 {
// par : để đi từ m->t
// child : để đi từ t->m
int par[N], child[N];
bool dfs_find(int u) { // có phải subtree chứa m ?
for (int v : g[u]) if (v != par[u]) {
par[v] = u;
if (dfs_find(v)) child[u] = v;
}
return child[u] || u == m;
}
int dfs_dp(int u, int p) {
if (g[u].size() == 1) return 0; // hết đường
if (g[u].size() == 2) return 1; // còn 1 đường nhưng sẽ bị chặn
vector<int> res;
for (int v : g[u]) if (v != p) {
res.push_back(dfs_dp(v, u) + 1); // nếu chuột chạy vào v thì min bước là ? (+1 lượt dọn phân khi quay lại)
}
sort(all(res), greater<int>());
return g[u].size() - 2 + res[1]; // chặn đường thứ nhất, chuột đi vào đường thứ nhì
}
vector<int> dp[N], path;
void getPath() {
int u = child[t], cnt(0);
while (u) {
cnt += max(0, (int)g[u].size() - 2 - (child[u] != 0));
path.push_back(u);
for (int v : g[u]) if (v != par[u] && v != child[u]) {
dp[u].push_back(dfs_dp(v, u) + 1 + cnt);
}
sort(all(dp[u]), greater<int>());
u = child[u];
}
}
bool check(int k) { // bắt được chuột trong k lượt?
priority_queue<int> q;
int cnt(0);
for (int u : path) {
++cnt; // tăng 1 lượt đặt chặn
for (int v : dp[u]) {
if (v < k) break;
if (cnt == 0) return false; // không thể chặn
--cnt, --k; // chặn và tốn 1 lượt
}
}
return true;
}
void solve() {
dfs_find(t);
getPath();
reverse(all(path)); // m->child[t]
int lo(0), hi(n * 2), mid;
while (lo <= hi) {
mid = (lo + hi) >> 1;
if (check(mid))
hi = mid - 1;
else lo = mid + 1;
}
cout << hi + 1 << '\n';
}
}
int main() {
cin.tie(NULL)->sync_with_stdio(false);
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);
}
if (checksubtask2())
subtask2::solve();
else subtask4::solve();
}
/** /\_/\
* (= ._.)
* / >0 \>1
**/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
47268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
369 ms |
79224 KB |
Output is correct |
| 2 |
Correct |
311 ms |
78372 KB |
Output is correct |
| 3 |
Correct |
718 ms |
82516 KB |
Output is correct |
| 4 |
Correct |
371 ms |
66328 KB |
Output is correct |
| 5 |
Correct |
785 ms |
82596 KB |
Output is correct |
| 6 |
Correct |
878 ms |
82464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
47268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
47268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
