#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)size(x))
#define all(x) begin(x), end(x)
#define trace(x) cout << #x << ": " << (x) << endl;
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }
template<typename T>
bool ckmn(T &x, T y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template<typename T>
bool ckmx(T &x, T y) {
if (x < y) {
x = y;
return true;
}
return false;
}
const int N = 1000001, infI = 1e9 + 7;
const ll infL = 3e18;
int n, t, m;
vector<int> g[N];
int dp[N], parent[N], depth[N], deg[N], gg[N], sum_deg[N];
vector<int> tops;
void dfs(int v, int p) {
parent[v] = p;
int mx1 = 0, mx2 = 0, cnt = 0;
deg[v] = (p == v ? sz(g[v]) : sz(g[v]) - 1);
sum_deg[v] = sum_deg[p] + deg[v];
for (int to: g[v]) {
if (to != p) {
++cnt;
depth[to] = depth[v] + 1;
dfs(to, v);
if (mx1 < dp[to]) {
mx2 = mx1;
mx1 = dp[to];
} else if (mx2 < dp[to]) {
mx2 = dp[to];
}
}
}
dp[v] = 1 + mx2 + (cnt - 1);
tops.push_back(v);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> t >> m;
--t, --m;
if (t == m) {
cout << 0;
return 0;
}
for (int i = 1; i < n; ++i) {
int a, b;
cin >> a >> b;
--a, --b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(t, t);
// cout << "dp:\n";
// for (int i = 0; i < n; ++i) cout << dp[i] << " ";
// cout << endl;
memset(gg, -1, sizeof(gg));
// trace(sum_deg[m] - depth[m])
{
int x = m, prv = -1;
while (x != t) {
for (int to: g[x]) {
if (to != parent[x] && to != prv) {
gg[to] = dp[to] + (x == m ? sum_deg[x] - depth[x] : sum_deg[x] - depth[x] - 1);
// cout << to << " " << gg[to] << endl;
}
}
prv = x;
x = parent[x];
}
}
int ans = infI;
for (int mid = 0; mid < 3 * n; ++mid) {
vector<int> pos;
vector<bool> used(n);
for (int x: tops) {
if (gg[x] > mid) {
pos.push_back(x);
}
}
int x = m;
int pnt = 0;
bool ok = true;
while (x != t) {
if (pnt < sz(pos)) {
used[pos[pnt++]] = true;
}
for (int to: g[x]) {
if (to != parent[x] && gg[to] > mid && !used[to]) {
ok = false;
break;
}
}
if (!ok) {
break;
}
x = parent[x];
}
if (ok) {
ans = min(ans, mid);
}
}
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
27648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5091 ms |
83016 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
27648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
27648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
