This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = (l); i < (r); ++i)
#define per(i, l, r) for (int i = (r - 1); i >= l; --i)
#define ALL(x) (x).begin(), (x).end()
using i64 = long long;
void main_() {
int N, T, M;
cin >> N >> T >> M;
--T, --M;
if (T == M) {
cout << 0 << endl;
return;
}
vector<int> A(N - 1), B(N - 1);
vector<vector<int>> Tree(N);
rep(i, 0, N - 1) {
cin >> A[i] >> B[i];
Tree[--A[i]].push_back(--B[i]);
Tree[B[i]].push_back(A[i]);
}
vector<bool> isPath(N);
vector<int> path;
auto dfs = [&](auto &&self, const int v, const int p) -> bool {
bool ret = false;
for (const int t : Tree[v]) {
if (t == p) continue;
ret |= self(self, t, v);
}
if (v == T) ret = true;
isPath[v] = ret;
if (ret) path.push_back(v);
return ret;
};
dfs(dfs, M, -1);
reverse(ALL(path));
vector<i64> dp(N);
auto dfs2 = [&](auto &&self, const int v, const int p) -> i64 {
vector<int> vals;
for (const int t : Tree[v]) {
if (t == p) continue;
if (isPath[t]) continue;
vals.push_back(self(self, t, v));
}
sort(ALL(vals), greater());
i64 cost = -1;
if (vals.empty()) cost = 0;
else if (vals.size() == 1) cost = 1;
else cost = vals[1] + (int)(vals.size()) - 1;
dp[v] = cost;
return dp[v] + 1;
};
i64 ans = 0;
bool isOk = false;
for (const auto e : path) {
if (e == T) continue;
if (isOk) {
ans += (int)Tree[e].size() - 2;
} else {
int cnt = (int)Tree[e].size() - 1 - (e == M ? 0 : 1);
if (cnt >= 1) {
ans += dfs2(dfs2, e, -1) - 1;
isOk = true;
}
}
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
main_();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |