#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];
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;
}
void solve(int v, int p) {
int children = 0;
for(auto u : adj[v]) {
if((u == p))
continue;
if(!(tin[u] <= tin[T] && tin[T] <= out[u]))
solve(u, v);
++children;
}
if(children == 0) leaves.push_back(v);
}
int dist(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
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];
}
int D = cur - dep[v] + dep[x];
return D;
}
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];
}
int res = 0;
for(auto u : leaves) {
res = max(res, dist(u, T));
}
cout << res << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
597 ms |
225568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
