#include <bits/stdc++.h>
using std::vector;
using std::array;
using std::pair;
using std::tuple;
template <class F> struct RecLambda : private F {
explicit RecLambda(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 i = 0; i < N - 1; ++i) {
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, -1);
RecLambda([&](auto&& dfs, const int u) -> void {
for (const int v : graph[u]) {
if (parent[u] != v) {
parent[v] = u;
dfs(v);
}
}
})(M);
vector<int> path;
for (int u = T; u != M;) {
path.push_back(u = parent[u]);
}
const int L = path.size();
vector<int> above(L);
for (int i = 0; i < L - 1; ++i) {
above[i + 1] = above[i] + (int)graph[path[i]].size() - 2;
}
vector<vector<int>> dp(L);
for (int i = 0, last = T; i < L; ++i) {
const int cur = path[i];
for (const int c : graph[i]) {
if (c != parent[cur] and c != last) {
dp[i].push_back(RecLambda([&](auto&& dfs, const int u, const int p) -> int {
vector<int> cand;
for (const int v : graph[u]) {
if (v != p) {
cand.push_back(dfs(v, u));
}
}
std::sort(cand.rbegin(), cand.rend());
const int size = (int)cand.size();
return size + (size <= 1 ? 0 : cand[1]);
})(c, cur));
}
}
last = cur;
}
const auto check = [&](const int thres) {
int sofar = 0;
for (int i = L - 1; i >= 0; --i) {
for (const int c : dp[i]) {
if (c + above[i] + sofar > thres) {
if (sofar > (L - i - 1)) {
return false;
}
sofar += 1;
}
}
}
return sofar <= 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 |
224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
337 ms |
72340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
