#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
const int MAXN = 3e5+5;
vector<pair<int,int>> path, temp;
vector<int> adj[MAXN];
int n,a,b;
pair<int,int> curEdge;
void dfs(int node, int p) {
if(!path.empty()) return;
if(node == b) {
path = temp;
return;
}
for(auto& u:adj[node]) {
if(u == p) continue;
temp.push_back({u,node});
dfs(u,node);
temp.pop_back();
}
}
int dfs1(int node, int p) {
int res = 0;
vector<int> c;
for(auto& u: adj[node]) {
if(u == p || (node == curEdge.F && u == curEdge.S) || (u == curEdge.F && node == curEdge.S)) continue;
c.push_back(dfs1(u,node));
}
sort(c.rbegin(), c.rend());
for(int i=0;i<c.size();i++) res = max(res, c[i]+i+1);
return res;
}
int main() {
scanf("%d%d%d", &n, &a, &b);
for(int i=0;i<n-1;i++) {
int u,v;
scanf("%d%d", &u,&v);
adj[u].push_back(v);
adj[v].push_back(u);
}
// figure out path
dfs(a,-1);
// figure out optimal split edge
int lo = 0, hi = path.size()-1, mid;
int ld = 0;
while(lo <= hi) {
mid = lo+hi>>1;
curEdge = path[mid];
int resa = dfs1(a,-1);
int resb = dfs1(b,-1);
if(resa <= resb) {
lo = mid+1;
ld = mid;
} else {
hi = mid-1;
}
}
int ans = 1e9;
int testIdx = ld;
if(testIdx >= 0 && testIdx < path.size()) {
curEdge = path[testIdx];
ans = min(ans, max(dfs1(a,-1), dfs1(b,-1)));
}
--testIdx;
if(testIdx >= 0 && testIdx < path.size()) {
curEdge = path[testIdx];
ans = min(ans, max(dfs1(a,-1), dfs1(b,-1)));
}
testIdx += 2;
if(testIdx >= 0 && testIdx < path.size()) {
curEdge = path[testIdx];
ans = min(ans, max(dfs1(a,-1), dfs1(b,-1)));
}
printf("%d",ans);
}
/*
6 2 1
1 2
2 3
2 4
1 5
5 6
10 1 2
1 2
2 5
1 3
1 4
4 6
6 7
3 8
3 9
3 10
17 1 2
1 3
1 4
4 6
6 7
3 8
3 9
3 10
1 13
13 5
13 11
13 12
13 14
14 15
15 16
15 17
14 2
*/
Compilation message
torrent.cpp: In function 'int dfs1(int, int)':
torrent.cpp:37:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int i=0;i<c.size();i++) res = max(res, c[i]+i+1);
| ~^~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:58:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
58 | mid = lo+hi>>1;
| ~~^~~
torrent.cpp:72:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | if(testIdx >= 0 && testIdx < path.size()) {
| ~~~~~~~~^~~~~~~~~~~~~
torrent.cpp:77:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | if(testIdx >= 0 && testIdx < path.size()) {
| ~~~~~~~~^~~~~~~~~~~~~
torrent.cpp:82:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | if(testIdx >= 0 && testIdx < path.size()) {
| ~~~~~~~~^~~~~~~~~~~~~
torrent.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
42 | scanf("%d%d%d", &n, &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
45 | scanf("%d%d", &u,&v);
| ~~~~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 3 |
Correct |
6 ms |
7424 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
609 ms |
20120 KB |
Output is correct |
| 2 |
Correct |
588 ms |
24788 KB |
Output is correct |
| 3 |
Correct |
565 ms |
25968 KB |
Output is correct |
| 4 |
Correct |
584 ms |
25584 KB |
Output is correct |
| 5 |
Correct |
558 ms |
22904 KB |
Output is correct |
| 6 |
Correct |
497 ms |
23596 KB |
Output is correct |
| 7 |
Correct |
487 ms |
26656 KB |
Output is correct |
