#include <bits/stdc++.h>
using namespace std;
vector <int> g[300010];
int u[300010], v[300010];
int vis;
int dp(int x, int par) {
// cout << x << " " << par << endl;
vector <int> a;
for(auto e : g[x]) {
int i = u[e] ^ v[e] ^ x;
if(e == vis) continue;
if(i == par) continue;
a.push_back(dp(i, x));
}
sort(a.begin(), a.end());
reverse(a.begin(), a.end());
int ans = 0;
for(unsigned i = 0; i < a.size(); i++) {
ans = max(ans, a[i] + int(i + 1));
}
return ans;
}
int pa[300010];
int d[300010];
const int inf = 1e9;
void dfs(int x, int par) {
for(auto e : g[x]) {
int i = u[e] ^ v[e] ^ x;
if(i == par) continue;
d[i] = 1 + d[x];
pa[i] = e;
dfs(i, x);
}
}
int a, b;
pair <int, int> func(int up) {
int cur = b;
while(up > 1) {
--up;
int e = pa[cur];
cur ^= u[e] ^ v[e];
}
vis = pa[cur];
return make_pair(dp(a, 0), dp(b, 0));
}
int search(int b, int e) {
if(b == e) {
pair <int, int> p = func(b);
return max(p.first, p.second);
}
if(e - b == 1) {
return min(search(b, b), search(e, e));
}
int m = (b + e) >> 1;
pair <int, int> p = func(m);
if(p.first - p.second >= 0) return search(m, e);
else return search(b, m - 1);
}
int find(int b, int e) {
if(b == e) {
pair <int, int> p = func(b);
return max(p.first, p.second);
}
if(e - b == 1) {
return min(find(b, b), find(e, e));
}
int m = (b + e) >> 1;
pair <int, int> p = func(m);
if(p.first - p.second <= 0) return find(m, e);
else return find(b, m - 1);
}
int main() {
int n;
scanf("%d %d %d", &n, &a, &b);
for(int i = 1; i < n; i++) {
int p, q;
scanf("%d %d", &p, &q);
g[p].push_back(i);
g[q].push_back(i);
u[i] = p;
v[i] = q;
}
dfs(a, 0);
/*
vector <int> vec;
for(int i = 1; i <= d[b]; i++) {
ans = min(ans, func(i));
vec.push_back(junk(i));
}
reverse(vec.begin(), vec.end());
assert(is_sorted(vec.begin(), vec.end()));
*/
int p = search(1, d[b]);
int q = find(1, d[b]);
printf("%d\n", min(p, q));
return 0;
}
Compilation message
torrent.cpp: In function 'int main()':
torrent.cpp:80:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &a, &b);
^
torrent.cpp:83:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &p, &q);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
13744 KB |
Output is correct |
| 2 |
Correct |
6 ms |
13744 KB |
Output is correct |
| 3 |
Correct |
0 ms |
13744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1166 ms |
25432 KB |
Output is correct |
| 2 |
Correct |
1263 ms |
26812 KB |
Output is correct |
| 3 |
Correct |
1126 ms |
28928 KB |
Output is correct |
| 4 |
Correct |
1143 ms |
27484 KB |
Output is correct |
| 5 |
Correct |
1143 ms |
25024 KB |
Output is correct |
| 6 |
Correct |
1069 ms |
25908 KB |
Output is correct |
| 7 |
Correct |
963 ms |
30144 KB |
Output is correct |
