// Be name khoda //
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define pb push_back
const int maxn5 = 1e6 + 10;
const int maxnt = 5e6 + 10;
const int inf = 1e9;
int tale, mo, dp[maxn5], id[maxn5], newid = 0;
int htotale[maxn5], st[maxn5], parr[maxn5];
int valu[maxn5], valval[maxn5], zz[maxn5];
int cmp[maxn5];
vector <int> adj[maxn5], ver;
vector <pair<int, int>> av;
pair <int, int> mx[maxnt];
int mn[maxnt], lazy[maxnt], lazy2[maxnt];
inline void build(int l, int r, int v){
if(r - l == 1){
mx[v] = {valu[l], l};
return;
}
int mid = (l + r) >> 1;
build(l, mid, v * 2);
build(mid, r, v * 2 + 1);
mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
return;
}
inline void build2(int l, int r, int v){
if(r - l == 1){
mn[v] = valval[l];
return;
}
int mid = (l + r) >> 1;
build2(l, mid, v * 2);
build2(mid, r, v * 2 + 1);
mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
return;
}
inline void add2(int l, int r, int lq, int rq, int v){
if(rq <= l || r <= lq)
return;
if(lq <= l && r <= rq){
mn[v]--;
lazy2[v]--;
return;
}
int mid = (l + r) >> 1;
add2(l, mid, lq, rq, v * 2);
add2(mid, r, lq, rq, v * 2 + 1);
mn[v] = min(mn[v * 2], mn[v * 2 + 1]) + lazy2[v];
return;
}
inline void add(int l, int r, int lq, int rq, int val, int v){
if(rq <= l || r <= lq)
return;
if(lq <= l && r <= rq){
mx[v].fi += val;
lazy[v] += val;
return;
}
int mid = (l + r) >> 1;
add(l, mid, lq, rq, val, v * 2);
add(mid, r, lq, rq, val, v * 2 + 1);
mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
mx[v].fi += lazy[v];
return;
}
inline bool dfs(int v, int par){
if(v == tale){
dp[v] = 0;
htotale[v] = 0;
return true;
}
int mx = 0, smx = 0;
int z = -1;
for(auto u : adj[v]) if(u != par){
bool re = dfs(u, v);
if(re){
z = u;
}
if(dp[u] >= mx){
smx = mx;
mx = dp[u];
}
else
smx = max(smx, dp[u]);
}
if(z == -1){
dp[v] = smx + adj[v].size() - 1;
//cout << "false " << v << ' ' << dp[v] << endl;
return false;
}
htotale[v] = htotale[z] + adj[v].size() - 2 + (v == mo);
ver.pb(v);
parr[v] = par;
zz[v] = z;
//ft[ver.size()] = newid;
return true;
}
inline bool ok(int v){
for(int i = v; i <= ver.size(); i++){
valval[i]--;
if(valval[i] < 0)
return false;
}
return true;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n, a, b; cin >> n >> a >> b;
a--; b--;
mo = b;
tale = a;
for(int i = 0; i < n - 1; i++){
int a, b; cin >> a >> b;
a--; b--;
adj[a].pb(b);
adj[b].pb(a);
}
//assert(a != b);
if(a == b)
return cout << 0 << endl, 0;
dfs(mo, -1);
reverse(all(ver)); // az m be t hast
//assert(ver.size() == 1);
int mxx = 0, smx = 0;
int pos = 1;
for(auto v : ver){
for(auto u : adj[v]) if(u != parr[v] && u != zz[v]){
cmp[newid] = pos;
valu[newid++] = dp[u] + htotale[v];
if(mxx <= dp[u] + htotale[v]){
smx = mxx;
mxx = dp[u] + htotale[v];
}
else
smx = max(smx, dp[u] + htotale[v]);
//cout << "aha " << v << ' ' << u << ' ' << dp[u] << ' ' << htotale[v] << endl;
}
st[pos] = newid;
pos++;
}
//return cout << min(inf, smx) << endl, 0;
build(0, newid, 1);
for(int i = 1; i <= ver.size(); i++)
valval[i] = i;
build2(0, ver.size() + 1, 1);
int done = 0;
int ans = inf;
//assert(st[pos - 1] == newid);
while(done < newid){
int z = -1;
for(int i = 0; i < newid; i++) if(z == -1 || valu[i] >= valu[z])
z = i;
//assert(done <= 1);
ans = min(ans, valu[z] + done);
//if(done == 1)
//assert(mx[1].fi + done == smx);
//if(done == 0)
//assert(mx[1].fi == mxx);
if(ok(cmp[z])){
done++;
for(int i = 0; i < st[cmp[z]]; i++)
valu[i]--;
valu[z] = -inf;
}
else
break;
}
//assert(done == 1);
cout << ans << endl;
}
Compilation message
mousetrap.cpp: In function 'bool ok(int)':
mousetrap.cpp:121:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(int i = v; i <= ver.size(); i++){
| ~~^~~~~~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:175:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
175 | for(int i = 1; i <= ver.size(); i++)
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23892 KB |
Output is correct |
| 2 |
Correct |
11 ms |
23892 KB |
Output is correct |
| 3 |
Runtime error |
302 ms |
524288 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
270 ms |
60240 KB |
Output is correct |
| 2 |
Correct |
262 ms |
56768 KB |
Output is correct |
| 3 |
Correct |
705 ms |
61288 KB |
Output is correct |
| 4 |
Correct |
341 ms |
43256 KB |
Output is correct |
| 5 |
Correct |
690 ms |
61232 KB |
Output is correct |
| 6 |
Correct |
667 ms |
61284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23892 KB |
Output is correct |
| 2 |
Correct |
11 ms |
23892 KB |
Output is correct |
| 3 |
Runtime error |
302 ms |
524288 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23892 KB |
Output is correct |
| 2 |
Correct |
11 ms |
23892 KB |
Output is correct |
| 3 |
Runtime error |
302 ms |
524288 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
