이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define pb emplace_back
#define SZ(val) (int)val.size()
#define all(val) val.begin(), val.end()
#define db(val) "[" #val " = " << (val) << "] "
const int maxn = 3e5 + 4;
struct Edge {
int u, v; bool used, bad;
int get(int x) {
return u ^ v ^ x;
}
Edge(int u = 0, int v = 0):
u(u), v(v) {
used = bad = 0;
}
};
int n, a, b, par[maxn], dp[maxn];
vector<int> adj[maxn];
vector<Edge> edges;
vector<int> myVec;
void dfs(int u, int p) {
for (int i : adj[u]) {
int v = edges[i].get(u);
if (v != p)
par[v] = i,
dfs(v, u);
}
}
void dfs(int u) {
vector<int> cur;
for (int i : adj[u]) if (!edges[i].used && !edges[i].bad) {
edges[i].used = 1;
int v = edges[i].get(u);
dfs(v);
cur.pb(v);
}
sort(all(cur), [&](int u, int v) {
return dp[u] > dp[v];
});
for (int i = 0; i < SZ(cur); i++)
dp[u] = max(dp[u], dp[cur[i]] + i + 1);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> a >> b;
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
adj[u].pb(i - 1);
adj[v].pb(i - 1);
edges.pb(u, v);
}
dfs(a, 0);
int u = b;
while (u != a) {
myVec.pb(par[u]);
u = edges[par[u]].get(u);
}
int L = 0, R = SZ(myVec) - 1, res = n;
while (L <= R) {
int m = (L + R) / 2;
for (int i = 0; i < SZ(myVec); i++)
edges[i].used = 0;
edges[myVec[m]].bad = 1;
dfs(a); dfs(b);
edges[myVec[m]].bad = 0;
res = min(res, max(dp[a], dp[b]));
if (dp[a] < dp[b]) L = m + 1;
else R = m - 1;
}
cout << res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |