#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 18;
const ll MAXN = 3e5 + 100;
vector<vector<int>> graph;
int a, b;
vector<int> path;
bool control = false;
void dfs(int node, int parent) {
path.push_back(node);
if (node == b)
control = true;
for (auto u : graph[node]) {
if (u == parent || control)
continue;
dfs(u, node);
}
if (!control)
path.pop_back();
}
int time(int node, int parent, int not_go) {
vector<int> t;
for (auto u : graph[node]) {
if (u == parent || u == not_go)
continue;
t.push_back(time(u, node, not_go));
}
sort(t.begin(), t.end(), greater<int>());
int mx = 0;
for (int i = 0; i < t.size(); i++)
mx = max(mx, t[i] + i + 1);
return mx;
}
pair<bool,int> check(int x) {
int t1 = time(a, a, path[x]);
int t2 = time(b, b, path[x-1]);
return {t2 >= t1, max(t1, t2)};
}
int main() {
fast
int n, u, v;
cin >> n >> a >> b;
graph = vector<vector<int>>(n+1, vector<int>());
for (int i = 1; i < n; i++) {
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
dfs(a, a);
int L = 1;
int R = path.size() - 1;
int ans = R;
while (R >= L) {
int mid = L + (R-L)/2;
if (check(mid).f) {
ans = mid;
R = mid - 1;
} else
L = mid + 1;
}
int q = check(ans).s;
if (ans != 1)
q = min(q, check(ans-1).s);
cout << q << "\n";
}
Compilation message
torrent.cpp: In function 'int time(int, int, int)':
torrent.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (int i = 0; i < t.size(); i++)
| ~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
500 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
268 ms |
23668 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |