#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+10;
int n, a, b;
vector< pair<int, int> > graph[maxn];
bool bio[maxn];
vector<int> path;
vector<int> q;
int dp1[maxn], dp2[maxn];
void dfs(int pos) {
bio[pos] = true;
if (pos == b) copy(q.begin(), q.end(), back_inserter(path));
else {
for (int i = 0; i < graph[pos].size(); i++) {
int tren = graph[pos][i].first;
if (!bio[tren]) {
q.push_back(graph[pos][i].second);
dfs(tren);
q.erase(q.end() - 1);
}
}
}
}
int err;
vector<int> dj[maxn];
int f(int pos) {
bio[pos] = true;
dj[pos].clear();
for (int i = 0; i < graph[pos].size(); i++) {
int tren = graph[pos][i].first;
int indx = graph[pos][i].second;
if (!bio[tren] && indx != err) dj[pos].push_back(f(tren));
}
int sol = 0;
sort(dj[pos].begin(), dj[pos].end());
reverse(dj[pos].begin(), dj[pos].end());
for (int i = 0; i < dj[pos].size(); i++)
sol = max(sol, dj[pos][i] + i + 1);
return sol;
}
int fa(int koj) {
//printf("fa: %d\n", koj);
if (dp1[koj] != -1) return dp1[koj];
err = koj;
memset(bio, false, sizeof bio);
dp1[koj] = f(a);
return dp1[koj];
}
int fb(int koj) {
//printf("fb: %d\n", koj);
if (dp2[koj] != -1) return dp2[koj];
err = koj;
memset(bio, false, sizeof bio);
dp2[koj] = f(b);
return dp2[koj];
}
inline int pred(int x) {
return x / abs(x);
}
int main() {
memset(bio, false, sizeof bio);
memset(dp1, -1, sizeof dp1);
memset(dp2, -1, sizeof dp2);
scanf("%d%d%d", &n, &a, &b);
for (int i = 1; i < n; i++) {
int x, y;
scanf("%d%d", &x, &y);
graph[x].push_back(make_pair(y, i));
graph[y].push_back(make_pair(x, i));
}
dfs(a);
int lo = 0, hi = path.size() - 1;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
int ac = fa(path[mid]);
int bc = fb(path[mid]);
if (ac == bc) {
printf("%d", ac);
return 0;
} else if (pred(ac - bc) != pred(fa(path[0]) - fb(path[0]))) hi = mid - 1;
else lo = mid;
}
//printf("GOOD\n");
int sol = max(fa(path[lo]), fb(path[lo]));
lo = 0, hi = path.size() - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
//printf("mid: %d\n", mid);
int ac = fa(path[mid]);
int bc = fb(path[mid]);
if (ac == bc) {
printf("%d", ac);
return 0;
} else if (pred(ac - bc) != pred(fa(path.back()) - fb(path.back()))) lo = mid + 1;
else hi = mid;
}
printf("%d", min(sol, max(fa(path[lo]), fb(path[lo]))));
return 0;
}
Compilation message
torrent.cpp: In function 'void dfs(int)':
torrent.cpp:17:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < graph[pos].size(); i++) {
~~^~~~~~~~~~~~~~~~~~~
torrent.cpp: In function 'int f(int)':
torrent.cpp:33:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < graph[pos].size(); i++) {
~~^~~~~~~~~~~~~~~~~~~
torrent.cpp:41:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < dj[pos].size(); i++)
~~^~~~~~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:73:10: 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:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
17152 KB |
Output is correct |
| 2 |
Correct |
11 ms |
17152 KB |
Output is correct |
| 3 |
Correct |
12 ms |
17152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
635 ms |
38564 KB |
Output is correct |
| 2 |
Correct |
650 ms |
40184 KB |
Output is correct |
| 3 |
Correct |
590 ms |
39668 KB |
Output is correct |
| 4 |
Correct |
585 ms |
41584 KB |
Output is correct |
| 5 |
Correct |
693 ms |
38776 KB |
Output is correct |
| 6 |
Correct |
558 ms |
38628 KB |
Output is correct |
| 7 |
Correct |
451 ms |
41576 KB |
Output is correct |
