#include "bits/stdc++.h"
using namespace std;
#define ar array
typedef int64_t ll;
//~ #define int ll
const int N = 1e6 + 5;
vector<int> edges[N];
int n, t, m, dp[N], is[N];
int c[N];
void dfs(int u, int p = -1){
is[u] = (u == t), c[u] = -1;
vector<int> t;
for(auto x : edges[u]){
if(x == p) continue;
dfs(x, u);
is[u] |= is[x];
if(!is[x]) t.push_back(x);
else c[u] = x;
}
sort(t.begin(), t.end(), [&](int& i, int& j){
return dp[i] > dp[j];
});
edges[u] = t;
if(t.empty()) dp[u] = 0;
else {
dp[u] = t.size();
if((int)t.size() > 1) dp[u] += dp[t[1]];
}
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>t>>m;
if(t == m){
cout<<0<<"\n";
return 0;
}
for(int i=1;i<n;i++){
int a, b; cin>>a>>b;
edges[a].push_back(b);
edges[b].push_back(a);
}
dfs(m);
int tot = 0, u = m;
vector<int> v;
while(u != t){
v.push_back(edges[u].size());
tot += edges[u].size();
u = c[u];
}
for(int i=(int)v.size() - 2;~i;i--){
v[i] += v[i+1];
} v.push_back(0);
auto check = [&](int mx){
int u = m, pos = 0, prev = 0, in = 0;
while(u != t){
pos++;
int rem = edges[u].size();
for(auto x : edges[u]){
if(dp[x] + prev + rem + v[in + 1] > mx) pos--, prev++;
rem--;
}
if(pos < 0) return false;
u = c[u], in++;
}
return true;
};
int l = tot, r = 1e9;
while(l < r){
int m = (l + r) >> 1;
if(check(m)) r = m;
else l = m + 1;
}
//~ while(m != t){
//~ pos++;
//~ vector<int>& t = edges[m];
//~ sort(t.begin(), t.end(), [&](int& i, int& j){
//~ return dp[i] > dp[j];
//~ });
//~ if(pos >= (int)t.size()){
//~ pos -= (int)t.size();
//~ res += (int)t.size();
//~ } else {
//~ res += dp[t[pos]] + (int)t.size();
//~ pos = 1e9;
//~ }
//~ m = c[m];
//~ }
cout<<l<<"\n";
}
/*
8 7 1
1 2
2 3
3 4
3 5
3 6
4 7
4 8
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23764 KB |
Output is correct |
3 |
Correct |
11 ms |
23720 KB |
Output is correct |
4 |
Correct |
12 ms |
23772 KB |
Output is correct |
5 |
Correct |
17 ms |
23744 KB |
Output is correct |
6 |
Correct |
14 ms |
23764 KB |
Output is correct |
7 |
Correct |
13 ms |
23820 KB |
Output is correct |
8 |
Correct |
13 ms |
23752 KB |
Output is correct |
9 |
Correct |
14 ms |
23764 KB |
Output is correct |
10 |
Correct |
14 ms |
23812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
312 ms |
66776 KB |
Output is correct |
2 |
Correct |
286 ms |
63484 KB |
Output is correct |
3 |
Correct |
815 ms |
69016 KB |
Output is correct |
4 |
Correct |
344 ms |
46912 KB |
Output is correct |
5 |
Correct |
841 ms |
68960 KB |
Output is correct |
6 |
Correct |
807 ms |
68940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23764 KB |
Output is correct |
3 |
Correct |
11 ms |
23720 KB |
Output is correct |
4 |
Correct |
12 ms |
23772 KB |
Output is correct |
5 |
Correct |
17 ms |
23744 KB |
Output is correct |
6 |
Correct |
14 ms |
23764 KB |
Output is correct |
7 |
Correct |
13 ms |
23820 KB |
Output is correct |
8 |
Correct |
13 ms |
23752 KB |
Output is correct |
9 |
Correct |
14 ms |
23764 KB |
Output is correct |
10 |
Correct |
14 ms |
23812 KB |
Output is correct |
11 |
Correct |
13 ms |
23764 KB |
Output is correct |
12 |
Correct |
14 ms |
23820 KB |
Output is correct |
13 |
Correct |
14 ms |
23764 KB |
Output is correct |
14 |
Correct |
13 ms |
24020 KB |
Output is correct |
15 |
Correct |
12 ms |
23892 KB |
Output is correct |
16 |
Correct |
17 ms |
23764 KB |
Output is correct |
17 |
Correct |
15 ms |
23764 KB |
Output is correct |
18 |
Correct |
15 ms |
23808 KB |
Output is correct |
19 |
Correct |
15 ms |
23788 KB |
Output is correct |
20 |
Correct |
12 ms |
23764 KB |
Output is correct |
21 |
Correct |
12 ms |
23868 KB |
Output is correct |
22 |
Correct |
12 ms |
23800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23764 KB |
Output is correct |
3 |
Correct |
11 ms |
23720 KB |
Output is correct |
4 |
Correct |
12 ms |
23772 KB |
Output is correct |
5 |
Correct |
17 ms |
23744 KB |
Output is correct |
6 |
Correct |
14 ms |
23764 KB |
Output is correct |
7 |
Correct |
13 ms |
23820 KB |
Output is correct |
8 |
Correct |
13 ms |
23752 KB |
Output is correct |
9 |
Correct |
14 ms |
23764 KB |
Output is correct |
10 |
Correct |
14 ms |
23812 KB |
Output is correct |
11 |
Correct |
312 ms |
66776 KB |
Output is correct |
12 |
Correct |
286 ms |
63484 KB |
Output is correct |
13 |
Correct |
815 ms |
69016 KB |
Output is correct |
14 |
Correct |
344 ms |
46912 KB |
Output is correct |
15 |
Correct |
841 ms |
68960 KB |
Output is correct |
16 |
Correct |
807 ms |
68940 KB |
Output is correct |
17 |
Correct |
13 ms |
23764 KB |
Output is correct |
18 |
Correct |
14 ms |
23820 KB |
Output is correct |
19 |
Correct |
14 ms |
23764 KB |
Output is correct |
20 |
Correct |
13 ms |
24020 KB |
Output is correct |
21 |
Correct |
12 ms |
23892 KB |
Output is correct |
22 |
Correct |
17 ms |
23764 KB |
Output is correct |
23 |
Correct |
15 ms |
23764 KB |
Output is correct |
24 |
Correct |
15 ms |
23808 KB |
Output is correct |
25 |
Correct |
15 ms |
23788 KB |
Output is correct |
26 |
Correct |
12 ms |
23764 KB |
Output is correct |
27 |
Correct |
12 ms |
23868 KB |
Output is correct |
28 |
Correct |
12 ms |
23800 KB |
Output is correct |
29 |
Correct |
12 ms |
23764 KB |
Output is correct |
30 |
Correct |
324 ms |
80140 KB |
Output is correct |
31 |
Correct |
335 ms |
80092 KB |
Output is correct |
32 |
Correct |
443 ms |
225400 KB |
Output is correct |
33 |
Correct |
426 ms |
221104 KB |
Output is correct |
34 |
Correct |
788 ms |
81128 KB |
Output is correct |
35 |
Correct |
787 ms |
81108 KB |
Output is correct |
36 |
Correct |
915 ms |
95784 KB |
Output is correct |
37 |
Correct |
896 ms |
95772 KB |
Output is correct |
38 |
Correct |
635 ms |
98632 KB |
Output is correct |
39 |
Correct |
637 ms |
98580 KB |
Output is correct |
40 |
Correct |
723 ms |
98612 KB |
Output is correct |