#include <bits/stdc++.h>
using namespace std;
const int INF = INT32_MAX;
const int LOG = 20;
int N, T, M;
int P[1000005][20], S[1000005][20], dep[1000005];
int timer, tin[1000005], out[1000005];
priority_queue<int, vector<int>, greater<int>> pq[1000005];
vector<int> leaves; vector<int> adj[1000005];
void dfs(int v, int p) {
P[v][0] = p; dep[v] = dep[p] + 1;
tin[v] = timer++;
int children = 0;
for(auto u : adj[v]) {
if(u == p) continue;
++children; dfs(u, v);
}
for(auto u : adj[v]) {
if(u == p) continue;
S[u][0] = children;
}
out[v] = timer - 1;
if(v == T && children == 0) pq[v].push(0);
}
void solve(int v, int p) {
int children = 0;
for(auto u : adj[v]) {
if((u == p))
continue;
if(u != T) solve(u, v);
++children;
}
if(children == 0) leaves.push_back(v);
}
int dist(int u, int v) {
bool swp = 0;
if(dep[u] < dep[v]) swap(u, v), swp = 1;
int K = dep[u] - dep[v];
int x = u, y = v, cur = 0;
for(int l = 0; l < LOG; l++)
if(K & (1 << l)) cur += S[x][l], x = P[x][l];
if(x != y) {
for(int l = LOG - 1; ~l; l--) {
if(P[x][l] != P[y][l]) {
cur += S[x][l], cur += S[y][l];
x = P[x][l], y = P[y][l];
}
}
cur += S[x][0]; x = P[x][0];
}
if(swp) swap(u, v);
int D = cur - dep[v] + dep[x];
return D;
}
void propagate(int v, int p) {
for(auto u : adj[v]) {
if(u == p) continue;
propagate(u, v);
pq[v].push({pq[u].top()});
while(pq[v].size() > 2) pq[v].pop();
}
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> T >> M;
for(int l = 0; l < N - 1; l++) {
int U, V; cin >> U >> V;
adj[U].push_back(V);
adj[V].push_back(U);
}
dep[M] = -1; dfs(M, M); solve(M, M);
for(int i = 1; i < LOG; i++)
for(int l = 1; l <= N; l++) {
P[l][i] = P[P[l][i - 1]][i - 1];
S[l][i] = S[l][i - 1] + S[P[l][i - 1]][i - 1];
}
for(auto u : leaves)
pq[u].push(dist(u, T));
propagate(M, M);
cout << pq[M].top();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
69 ms |
111564 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
673 ms |
288044 KB |
Output is correct |
| 2 |
Correct |
619 ms |
264740 KB |
Output is correct |
| 3 |
Incorrect |
1587 ms |
289364 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
69 ms |
111564 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
69 ms |
111564 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
