#include <bits/stdc++.h>
#define int long long
using namespace std;
#ifdef LOCAL
#define dbg(x) cerr << x << "\n";
#else
#define dbg(x)
#endif
const int INF = 1e17;
int n, t, m;
vector<int> scores;
vector<vector<int>> g;
vector<int> depths;
int dfs1(int v, int p) {
depths[v] = depths[p] + 1;
vector<int> besties;
for (int w : g[v]) {
if (w == p)
continue;
besties.push_back(dfs1(w, v));
}
sort(besties.begin(), besties.end());
int score = max((int)g[v].size() - 1, 1ll);
if (besties.size() >= 2) {
score += besties[besties.size() - 2];
}
return scores[v] = score;
}
int dfs2(int v, int p, int blocks) {
dbg("v " << v << " blocks " << blocks);
int score = INF;
if (v == m) {
return blocks + scores[v];
}
blocks += g[v].size() - 2;
for (int w : g[v]) {
if (w == p)
continue;
score = min(dfs2(w, v, blocks), score);
dbg("current score: " << score);
}
if (v == t)
return score;
if (score != INF) {
return min(score, blocks - 1 + scores[v]);
}
return INF;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> t >> m;
t--;
m--;
g.resize(n);
scores.resize(n);
depths.resize(n);
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
a--;
b--;
g[a].push_back(b);
g[b].push_back(a);
}
depths[t] = 0;
dfs1(t, t);
cout << dfs2(t, t, -g[t].size() + 2) << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
389 ms |
78596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
