#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define ll long long
#define db double
#define ii pair<int,int>
#define f first
#define s second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define all(v) v.begin(),v.end()
#define BIT(i) ((ll)1<<(i))
#define debug(x) for (auto p: x) cout<<p<<' ';cout<<endl
#define forw(i,j,z) for(int i=(int)j;i<=(int)z;i++)
#define ford(i,j,z) for (int i=(int)j;i>=(int)z;i--)
#define sz(a) (int)a.size()
#define len(a) (int)a.length()
#define fIlE "test."
const int mod = 998244353;
inline int add(int u,int v){u+=v;if(u>=mod)u-=mod;return u;}
//auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
//mt19937 RAND(seed);
inline int dec(int u,int v){u-=v;if(u<0)u+=mod;return u;}
inline int mul(int u,int v){return (ll)u*v%mod;}
const int N = 3e5 + 1;
vector<int> a[N];
int nxt[N];
ii edge[N];
int h[N];
int n, A, B;
bool del[N];
void fdfs(int u = 1, int par = 0)
{
for (int i : a[u])
if (i != par){
{
int v = edge[i].f == u ? edge[i].s : edge[i].f;
nxt[v] = i;
h[v] = h[u] + 1;
fdfs(v, i);
}
}
}
vector<int> ok(int u, int v)
{
vector<int> p, t;
while(h[u] < h[v])
{
t.pb(nxt[v]);
v = edge[nxt[v]].f == v ? edge[nxt[v]].s : edge[nxt[v]].f;
}
while(h[u] > h[v])
{
p.pb(nxt[u]);
u = edge[nxt[u]].f == u ? edge[nxt[u]].s : edge[nxt[u]].f;
}
while(u != v)
{
t.pb(nxt[v]);
v = edge[nxt[v]].f == v ? edge[nxt[v]].s : edge[nxt[v]].f;
p.pb(nxt[u]);
u = edge[nxt[u]].f == u ? edge[nxt[u]].s : edge[nxt[u]].f;
}
reverse(all(t));
int _ = sz(p);
p.resize(sz(p) + sz(t));
copy(all(t), begin(p) + _);
return p;
}
int f(int u, int par = 0)
{
vector<int> cal;
for (int i : a[u]) if (i != par && !del[i])
{
int v = edge[i].f == u ? edge[i].s : edge[i].f;
cal.pb(f(v, i));
}
int ans = 0;
sort(all(cal), greater<int>());
forw(i, 0, sz(cal) - 1)
ans = max(ans, i + 1 + cal[i]);
return ans;
}
void solve()
{
cin >> n >> A >> B;
for (int i = 1; i < n; ++i){
int x, y;
cin >> x >> y;
edge[i] = mp(x, y);
a[x].pb(i);
a[y].pb(i);
}
fdfs();
vector<int> List = ok(A, B);
int l = 0, r = sz(List) - 1, ans = n;
while(l <= r)
{
int mid = (l + r) >> 1;
del[List[mid]] = 1;
int la = f(A), lb = f(B);
ans = min(ans, max(la, lb));
if (la < lb)
l = mid + 1;
else r = mid - 1;
del[List[mid]] = 0;
}
cout << ans;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
if (fopen(fIlE"inp", "r"))
freopen(fIlE"inp","r",stdin), freopen(fIlE"out","w",stdout);
//time_t TIME_TU=clock();
int t=1;
// cin>>t;
while(t--)
solve();
//time_t TIME_TV=clock();
//cerr<<(db)(TIME_TV-TIME_TU)/CLOCKS_PER_SEC<<endl;
return 0;
}
Compilation message
torrent.cpp: In function 'int main()':
torrent.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
116 | freopen(fIlE"inp","r",stdin), freopen(fIlE"out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
torrent.cpp:116:46: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
116 | freopen(fIlE"inp","r",stdin), freopen(fIlE"out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
7512 KB |
Output is correct |
| 2 |
Correct |
3 ms |
7516 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7516 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
225 ms |
28756 KB |
Output is correct |
| 2 |
Correct |
234 ms |
30736 KB |
Output is correct |
| 3 |
Correct |
241 ms |
31504 KB |
Output is correct |
| 4 |
Correct |
240 ms |
31980 KB |
Output is correct |
| 5 |
Correct |
238 ms |
28156 KB |
Output is correct |
| 6 |
Correct |
214 ms |
28496 KB |
Output is correct |
| 7 |
Correct |
211 ms |
32144 KB |
Output is correct |
