#include <bits/stdc++.h>
using std::vector;
template <class F> struct fixed : private F {
explicit fixed(F&& f) : F(std::forward<F>(f)) {}
template <class... Args> decltype(auto) operator()(Args&&... args) const {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, T, M;
std::cin >> N >> T >> M;
T -= 1, M -= 1;
vector<vector<int>> graph(N);
for (int e = 1; e < N; ++e) {
int a, b;
std::cin >> a >> b;
a -= 1, b -= 1;
graph[a].push_back(b);
graph[b].push_back(a);
}
vector<int> parent(N);
parent[T] = -1;
fixed([&](auto&& dfs, const int u) -> void {
for (const int v : graph[u]) {
if (v != parent[u]) {
parent[v] = u;
dfs(v);
}
}
})(T);
vector<int> path;
vector<char> on_path(N);
for (int u = M; u != -1; u = parent[u]) {
path.push_back(u);
on_path[u] = true;
}
const int L = (int)path.size();
vector<vector<int>> dp(L);
for (int i = 0; i < L; ++i) {
for (const int src : graph[path[i]]) {
if (!on_path[src]) {
dp[i].push_back(fixed([&](auto&& dfs, const int u) -> int {
vector<int> list;
for (const int v : graph[u]) {
if (v != parent[u]) {
list.push_back(dfs(v));
}
}
const int n = (int)list.size();
std::sort(list.rbegin(), list.rend());
return (n >= 2 ? list[1] : 0) + n + 1;
})(src));
}
}
}
vector<int> above(L);
above[L - 1] = (int)graph[T].size() - 1;
for (int i = L - 2; i >= 0; --i) {
above[i] = above[i + 1] + (int)graph[path[i]].size() - 2;
}
const auto check = [&](const int thres) {
int cut = 0;
for (int i = 0; i < L; ++i) {
const int offset = cut + above[i];
for (const int x : dp[i]) {
if (offset + x > thres) {
if (cut > i) {
return false;
}
cut += 1;
}
}
}
return cut <= thres;
};
int ok = N, ng = -1;
while (ok - ng > 1) {
const int md = (ok + ng) / 2;
(check(md) ? ok : ng) = md;
}
std::cout << ok << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
318 ms |
73356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
