#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) {
bool flag = false;
depths[v] = depths[p] + max(0ll, (int)g[v].size() - 2);
if (v == t) {
depths[v] = 0;
}
vector<int> besties;
for (int w : g[v]) {
if (w == p)
continue;
int thisscore = dfs1(w, v);
if (thisscore < 0) {
flag = true;
continue;
}
besties.push_back(dfs1(w, v));
}
sort(besties.begin(), besties.end());
int score = besties.size();
if ((int)g[v].size() == 1)
score = 1;
if (v == t) {
score = 0;
}
if (besties.size() >= 2) {
score += besties[besties.size() - 2];
}
scores[v] = score;
if (v == m || flag) {
return -score;
}
return score;
}
int dfs2(int v, int p) {
dbg("v " << v << " blocks " << depths[p]);
int score = -INF;
if (v == m) {
score = 0;
dbg("heerer " << depths[p] + scores[v]);
for (int w : g[v]) {
if (w == p)
continue;
score = max(depths[v] + scores[w] + 1, score);
}
dbg("Score at m: " << score);
return score;
}
for (int w : g[v]) {
if (w == p)
continue;
score = max(dfs2(w, v), score);
dbg("current score #" << w << ": " << score);
}
if (score != -INF) {
return max(score, depths[p] - 2 + scores[v]);
}
return -INF;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> t >> m;
t--;
m--;
if (t == m) {
cout << "0\n";
exit(0);
}
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);
}
while (g[m].size() == 1) {
int tmp = m;
m = g[m][0];
g[tmp].clear();
auto it = find(g[m].begin(), g[m].end(), tmp);
g[m].erase(it, it + 1);
if (t == m) {
cout << "0\n";
exit(0);
}
}
depths[t] = 1;
dfs1(t, t);
dbg("scores");
for (int i = 0; i < n; i++) {
cout << scores[i] << " ";
}
cout << "\n";
dbg("depths");
for (int i = 0; i < n; i++) {
cout << depths[i] << " ";
}
cout << "\n";
cout << dfs2(t, t) << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5049 ms |
78476 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
