#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 3e5 + 7;
const int LOG = 18;
vector<pair<int, int>> G[MAXN];
int wsk[MAXN];
int depth[MAXN];
int dp[MAXN];
bool blocked[MAXN];
int jmp[MAXN][LOG + 1];
int root1, root2;
int res;
int n;
bool cmp(pair<int ,int> a, pair<int, int> b){
return dp[a.first] > dp[b.first];
}
void dfs(int v, int p, int d = 0){
depth[v] = d;
jmp[v][0] = p;
for(int k = 1; k <= LOG; k++)
jmp[v][k] = jmp[jmp[v][k-1]][k-1];
for(auto [u, id] : G[v]){
if(u == p) continue;
wsk[u] = id;
dfs(u, v, d+1);
}
}
void dfs_res(int v, int p){
dp[v] = 0;
for(auto [u, id] : G[v]){
if(u == root1 || u == root2 || blocked[id] || u == p) continue;
dfs_res(u, v);
}
sort(G[v].begin(), G[v].end(), cmp);
int add = 1;
for(auto [u, id] : G[v]){
if(u == root1 || u == root2 || blocked[id] || u == p) continue;
dp[v] = max(dp[v], dp[u] + add);
add++;
}
}
void solve(){
int v = root1;
int u = root2;
for(int k = LOG; k >= 0; k--){
blocked[wsk[jmp[u][k]]] = true;
dfs_res(root1, root1);
dfs_res(root2, root2);
if(depth[v] < depth[jmp[u][k]] && max(dp[root1], dp[root2]) <= res){
blocked[wsk[jmp[u][k]]] = false;
res = max(dp[root1], dp[root2]);
//u = jmp[u][k];
}
blocked[wsk[jmp[u][k]]] = false;
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
cin >> root1 >> root2;
for(int i = 1; i < n; i++){
int a, b;
cin >> a >> b;
G[a].push_back({b, i});
G[b].push_back({a, i});
}
dfs(root1, root1);
dfs_res(root1, root1);
dfs_res(root2, root2);
res = max(dp[root1], dp[root2]);
/*
for(int i = 1; i <= n; i++){
blocked[wsk[i]] = true;
dfs_res(root1, root1);
dfs_res(root2, root2);
res = min(res, max(dp[root1], dp[root2]));
blocked[wsk[i]] = false;
}
*/
solve();
cout << res << endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
7452 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
591 ms |
47012 KB |
Output is correct |
2 |
Correct |
629 ms |
48772 KB |
Output is correct |
3 |
Incorrect |
524 ms |
48440 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |