// 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 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 + int(adj[v].size()) - 1;
//cout << "false " << v << ' ' << dp[v] << endl;
return false;
}
htotale[v] = htotale[z] + int(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];
cout << v << ' ' << u << ' ' << dp[u] << ' ' << htotale[v] << endl;
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);
//cout << newid << endl;
if(newid == 0){
return cout << 0 << endl, 0;
}
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;
}
if(done == newid)
ans = min(ans, done);
//assert(done == 1);
cout << ans << endl;
}
Compilation message
mousetrap.cpp: In function 'bool ok(int)':
mousetrap.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int i = v; i <= ver.size(); i++){
| ~~^~~~~~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:120:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for(int i = 1; i <= ver.size(); i++)
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
282 ms |
67472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
