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;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
if (n == 1) {
cout << 0 << '\n';
return 0;
}
vector<vector<int>> adj(n);
for (int i = 0; i < n - 1; i += 1) {
int a, b;
cin >> a >> b;
a -= 1, b -= 1;
adj[a].push_back(b);
adj[b].push_back(a);
}
vector<pair<int, int>> dp(n);
function<pair<int, int>(int, int)> Dfs = [&](int node, int pre) {
int ans = 1;
for (auto x : adj[node]) {
if (x == pre) continue;
ans += Dfs(x, node).first;
}
return dp[node] = make_pair(ans, pre);
};
Dfs(0, -1);
long long ans = 0;
int max_depth = 0;
function<void(int, int, int, int, bool)> Get = [&](int node, int pre, int depth, int sub, bool now) {
if (now) {
max_depth = max(depth, max_depth);
}
ans += 1LL * depth * 2;
for (auto x : adj[node]) {
if (x == pre) continue;
bool c1 = (x == sub || sub == -1);
Get(x, node, depth + 1, sub, now | c1);
}
return;
};
auto Init = [&]() {
max_depth = 0;
ans = 0;
return;
};
vector<int> sum(n);
for (int i = 0; i < n; i++) {
for (auto x : adj[i]) {
if (x == dp[i].second) continue;
sum[i] += dp[x].first;
}
}
for (int node = 0; node < n; node += 1) {
vector<pair<int, int>> comps;
int id = 0, cnt = 0;
for (auto x : adj[node]) {
int sz = (x == dp[node].second ? n - 1 - sum[node] : dp[x].first);
comps.emplace_back(sz, x);
if (comps[id].first <= sz) {
id = cnt;
}
cnt += 1;
}
int mx = comps[id].first;
int sub = comps[id].second;
if (mx > n - mx) {
cout << -1 << '\n';
continue;
}
else {
if (n - 2 * mx == 0) {
Get(node, -1, 0, sub, 0);
}
else {
Get(node, -1, 0, -1, 0);
}
cout << ans - max_depth << '\n';
Init();
}
}
return 0;
}
# | 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... |
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |