#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " " <<
typedef long long ll;
typedef pair<int, int> point;
const int MAXN = 3e5 + 5;
vector <int> edge[MAXN];
int n, a, b;
void load(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> a >> b;
REP(i, n - 1){
int x, y; cin >> x >> y;
edge[x].push_back(y);
edge[y].push_back(x);
}
}
int par[MAXN];
void find_path(int x){
for(auto it : edge[x]){
if(it == par[x]) continue;
par[it] = x;
find_path(it);
}
}
vector <int> path;
void create_path(){
for(int i = b; i != a; i = par[i])
path.push_back(i);
}
int cutEdge;
int calc(int curr, int par = 0){
vector <int> v;
for(auto it : edge[curr]){
if(it == par) continue;
if(it == cutEdge) continue;
v.push_back(calc(it, curr));
}
int ret = 0;
REP(i, (int)v.size())
ret = max(ret, v[i] + i + 1);
return ret;
}
void solve(){
int lo = 0, hi = path.size() - 1;
int last = 0;
while(lo < hi){
int mid = (lo + hi) >> 1;
cutEdge = path[mid];
int left = calc(a);
int right = calc(b);
if(left < right){
lo = mid + 1;
last = mid;
}
else
hi = mid - 1;
}
//TRACE(lo); TRACE(last);
cutEdge = path[last];
int sol = max(calc(a), calc(b));
if(last + 1 < path.size()){
cutEdge = path[last + 1];
sol = min(sol, max(calc(a), calc(b)));
}
cout << sol - 1;
}
int main(){
load();
find_path(a);
create_path();
solve();
}
Compilation message
torrent.cpp: In function 'void solve()':
torrent.cpp:83:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(last + 1 < path.size()){
~~~~~~~~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
9 ms |
7416 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
583 ms |
25760 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |