이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
#define pb push_back
#define ep emplace
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define mem(f,x) memset(f , x , sizeof(f))
#define sz(x) (ll)(x).size()
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define mxx *max_element
#define mnn *min_element
#define cntbit(x) __builtin_popcountll(x)
#define len(x) (int)(x.length())
const int N = 3e5 + 10;
vector <pair <int, int>> ed[N];
int par[N], in[N], ou[N], id[N], timer = 1;
int dp[N];
void dfs(int u, int v) {
in[u] = ++timer;
for (auto x : ed[u]) {
if (x.f == v)
continue;
par[x.f] = u;
id[x.f] = x.s;
dfs(x.f, u);
}
ou[u] = timer;
}
bool is(int a, int b) {
return in[a] <= in[b] && ou[a] >= ou[b];
}
vector <int> path(int a, int b) {
vector <int> L;
while (is(a, b) == 0) {
L.pb(id[a]);
a = par[a];
}
vector <int> R;
while (a != b) {
R.pb(id[b]);
b = par[b];
}
reverse(all(R));
for (auto x : R)
L.pb(x);
return L;
}
void dq(int u, int v, int ban) {
dp[u] = 0;
vector <int> lst;
for (auto x : ed[u]) {
if (x.f == v || x.s == ban)
continue;
dq(x.f, u, ban);
lst.pb(dp[x.f]);
}
sort(all(lst), greater <int> ());
int c = 1;
for (auto x : lst) {
dp[u] = max(x + c, dp[u]);
c++;
}
}
int solve(int x, int ban) {
dq(x, x, ban);
return dp[x];
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, a, b;
cin >> n >> a >> b;
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
ed[x].pb({y, i});
ed[y].pb({x, i});
}
dfs(1, 1);
vector <int> road = path(a, b);
int ans = 1e9, l = 0, r = sz(road) - 1, m;
while (l <= r) {
m = (l + r) / 2;
int A = solve(a, road[m]), B = solve(b, road[m]);
if (A <= B) {
l = m + 1;
} else {
r = m - 1;
}
ans = min(ans, max(A, B));
}
cout << ans << '\n';
return 0;
}
/*
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
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |