// #include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <string>
#include <functional>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <climits>
#include <cstdlib>
#include <bitset>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ld, ld> pdd;
const ll INF=1000000007;
const ll INFL=1000000000000000007;
const ld INFS=0.00000001;
const ll MOD=1000000007;
const ld PI=3.14159265;
const int dir[4][2]={{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
const int dir2[8][2]={{1, 1}, {1, 0}, {1, -1}, {0, 1}, {0, -1}, {-1, 1}, {-1, 0}, {-1, -1}};
// CODE
int n, a, b;
vector<int> con[300001];
vector<int> son[300001];
int father[300001];
int dp[300001];
int dp2[300001];
bool evil[300001];
void rec(int x, int nope)
{
vector<int> need;
int i;
for(i=0;i<son[x].size();i++)
rec(son[x][i], nope);
for(i=0;i<son[x].size();i++){
int f=son[x][i];
if(f!=nope)
need.pb(dp2[f]);
}
sort(need.begin(), need.end());
int cur=1;
for(i=int(need.size())-1;i>=0;i--)
dp2[x]=max(dp2[x], need[i]+cur), cur++;
}
int ok(int x)
{
int i;
for(i=1;i<=n;i++)
dp2[i]=0;
int time=0;
int pos=b, pos2=b;
while(dp[pos]+time<=x){
if(dp[pos]+time==x){
vector<int> need;
for(i=0;i<son[pos].size();i++){
int f=son[pos][i];
if(f!=pos2)
need.pb(dp[f]);
}
sort(need.begin(), need.end());
for(i=int(need.size())-1;i>=0;i--){
int f=need[i];
if(f+time<x)
break;
time++;
}
pos2=pos, pos=father[pos], time++;
}
else
pos2=pos, pos=father[pos], time++;
}
rec(a, pos2);
if(dp2[a]<=x)
return 1;
return 0;
}
void wk(int x)
{
vector<int> need;
int i;
for(i=0;i<son[x].size();i++)
wk(son[x][i]);
for(i=0;i<son[x].size();i++){
int f=son[x][i];
if(!evil[f])
need.pb(dp[f]);
}
sort(need.begin(), need.end());
int cur=1;
for(i=int(need.size())-1;i>=0;i--)
dp[x]=max(dp[x], need[i]+cur), cur++;
}
void rt(int x, int fa)
{
int i;
for(i=0;i<con[x].size();i++){
int f=con[x][i];
if(f!=fa)
son[x].pb(f), father[f]=x, rt(f, x);
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int i;
cin >> n >> a >> b;
for(i=1;i<n;i++){
int x, y;
cin >> x >> y;
con[x].pb(y);
con[y].pb(x);
}
rt(a, -1);
int cur=b;
while(cur!=a)
evil[cur]=true, cur=father[cur];
wk(a);
int lo=dp[b], hi=n, m;
while(lo<hi){
m=(lo+hi)/2;
if(!ok(m))
lo=m+1;
else
hi=m;
}
cout << lo << endl;
return 0;
}
Compilation message
torrent.cpp: In function 'void rec(int, int)':
torrent.cpp:57:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(i=0;i<son[x].size();i++)
| ~^~~~~~~~~~~~~~
torrent.cpp:59:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(i=0;i<son[x].size();i++){
| ~^~~~~~~~~~~~~~
torrent.cpp: In function 'int ok(int)':
torrent.cpp:81:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for(i=0;i<son[pos].size();i++){
| ~^~~~~~~~~~~~~~~~
torrent.cpp: In function 'void wk(int)':
torrent.cpp:110:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for(i=0;i<son[x].size();i++)
| ~^~~~~~~~~~~~~~
torrent.cpp:112:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for(i=0;i<son[x].size();i++){
| ~^~~~~~~~~~~~~~
torrent.cpp: In function 'void rt(int, int)':
torrent.cpp:127:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for(i=0;i<con[x].size();i++){
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14464 KB |
Output is correct |
| 2 |
Correct |
11 ms |
14464 KB |
Output is correct |
| 3 |
Correct |
10 ms |
14464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
478 ms |
36856 KB |
Output is correct |
| 2 |
Correct |
478 ms |
38072 KB |
Output is correct |
| 3 |
Correct |
432 ms |
39288 KB |
Output is correct |
| 4 |
Correct |
484 ms |
39352 KB |
Output is correct |
| 5 |
Correct |
518 ms |
37244 KB |
Output is correct |
| 6 |
Correct |
476 ms |
37936 KB |
Output is correct |
| 7 |
Correct |
459 ms |
40744 KB |
Output is correct |
