#include <bits/stdc++.h>
using namespace std;
#define REP(i, j, k) for (int i = (j); i < (k); i++)
#define RREP(i, j, k) for (int i = (j); i >= (k); i--)
template <class T>
inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int) x.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef tuple<int, int, int> iii;
typedef vector<iii> viii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
const int INF = 1000000005;
const ll LINF = 1000000000000000005;
const int MAXN = 300005;
int n, a, b;
vi adj[MAXN];
int pre[MAXN], pst[MAXN], ptr;
void dfs(int u, int p) {
pre[u] = ptr++;
for (int v : adj[u]) {
if (v == p) {
continue;
}
dfs(v, u);
}
pst[u] = ptr;
}
int pmx[MAXN], smx[MAXN];
int memo1[MAXN];
bool done[MAXN];
void dp1(int u, int p, int x) {
int funny = 0;
vi ch;
for (int v : adj[u]) {
if (v == p) {
continue;
}
if (pre[v] <= pre[b] && pre[b] < pst[v]) {
funny = v;
continue;
}
ch.pb(v);
dp1(v, u, x);
}
sort(ALL(ch), [&] (int l, int r) {
return memo1[l] > memo1[r];
});
if (!funny) {
REP (i, 0, SZ(ch)) {
mxto(memo1[u], memo1[ch[i]] + i + 1);
}
return;
}
cerr << u << ' ' << p << ' ' << x << '\n';
REP (i, 0, SZ(ch)) {
cerr << ' ' << ch[i] << ": " << memo1[ch[i]] << '\n';
}
REP (i, 0, SZ(ch)) {
pmx[i] = memo1[ch[i]] + i + 1;
if (i) {
mxto(pmx[i], pmx[i - 1]);
}
cerr << ' ' << i << ": " << pmx[i] << '\n';
}
RREP (i, SZ(ch) - 1, 0) {
smx[i] = memo1[ch[i]] + i + 2;
if (i + 1 != SZ(ch)) {
mxto(smx[i], smx[i + 1]);
}
cerr << ' ' << i << ": " << smx[i] << '\n';
}
int gd = -1;
REP (i, 0, SZ(ch) + 1) {
int cmx = 0;
if (i) {
mxto(cmx, pmx[i - 1]);
}
if (i != SZ(ch)) {
mxto(cmx, smx[i]);
}
cerr << " " << i << ": " << cmx << '\n';
if (cmx <= x) {
gd = i;
break;
}
}
if (gd == -1) {
return;
}
done[u] = 1;
dp1(funny, u, x - (gd + 1));
}
int memo2[MAXN];
void dp2(int u, int p) {
vi ch;
for (int v : adj[u]) {
if (v == p || done[v]) {
continue;
}
ch.pb(v);
dp2(v, u);
}
sort(ALL(ch), [&] (int l, int r) {
return memo2[l] > memo2[r];
});
REP (i, 0, SZ(ch)) {
mxto(memo2[u], memo2[ch[i]] + i + 1);
}
}
bool isPos(int x) {
REP (i, 1, n + 1) {
done[i] = 0;
memo1[i] = 0;
memo2[i] = 0;
}
dp1(a, -1, x);
if (!done[a]) {
return 0;
}
dp2(b, -1);
return memo2[b] <= x;
}
int main() {
#ifndef DEBUG
ios::sync_with_stdio(0), cin.tie(0);
#endif
cin >> n >> a >> b;
REP (i, 1, n) {
int u, v; cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
if (n == 2) {
cout << 0 << '\n';
return 0;
}
dfs(a, -1);
int lo = 1, hi = n, mid;
while (lo < hi) {
mid = lo + hi >> 1;
if (isPos(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
cout << hi << '\n';
return 0;
}
Compilation message
torrent.cpp: In function 'int main()':
torrent.cpp:165:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
165 | mid = lo + hi >> 1;
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
478 ms |
26912 KB |
Output is correct |
| 2 |
Correct |
486 ms |
30428 KB |
Output is correct |
| 3 |
Correct |
366 ms |
31332 KB |
Output is correct |
| 4 |
Correct |
491 ms |
32768 KB |
Output is correct |
| 5 |
Correct |
442 ms |
26144 KB |
Output is correct |
| 6 |
Correct |
352 ms |
26248 KB |
Output is correct |
| 7 |
Correct |
309 ms |
32040 KB |
Output is correct |
