2024年3月22日发(作者：郁冬梅)
if(q[pos] == b[i]) {
if(mp[b[i]] > 1) {
ans = min(ans, b[i].second + q[pos].second + (n - b[i].first - q[pos].first) * (n - b[i].first - q[pos].first));
} else {
if(pos < r) ans = min(ans, b[i].second + q[pos + 1].second + (n - b[i].first - q[pos + 1].first) * (n - b[i].first - q[pos + 1].first));
else ans = min(ans, b[i].second + q[pos - 1].second + (n - b[i].first - q[pos - 1].first) * (n - b[i].first - q[pos - 1].first));
}
} else {
ans = min(ans, b[i].second + q[pos].second + (n - b[i].first - q[pos].first) * (n - b[i].first - q[pos].first));
}
}
}
for (int i = 1; i <= tot; i++) {
ans = min(ans, b[i].second + (n - b[i].first) * (n - b[i].first));
}
if(fa != -1 && G[x].size() == 1) dp[x] = sz[x] * sz[x];
a[x] = make_pair(sz[x], dp[x]);
}
int main() {
int x, y;
memset(dp, 0x3f, sizeof(dp));
// freopen("", "r", stdin);
// freopen("", "w", stdout);
scanf("%lld", &n);
for (int i = 1; i < n; i++) {
scanf("%d%d", &x, &y);
add(x, y);
}
ans = 1e18;
dfs(1, -1);
ans = min(ans, dp[1]);
ans -= n;
ans /= 2;
ans = 2ll * n * (n - 1) / 2ll - ans;
printf("%lldn", ans);
}
2024年3月22日发(作者：郁冬梅)
if(q[pos] == b[i]) {
if(mp[b[i]] > 1) {
ans = min(ans, b[i].second + q[pos].second + (n - b[i].first - q[pos].first) * (n - b[i].first - q[pos].first));
} else {
if(pos < r) ans = min(ans, b[i].second + q[pos + 1].second + (n - b[i].first - q[pos + 1].first) * (n - b[i].first - q[pos + 1].first));
else ans = min(ans, b[i].second + q[pos - 1].second + (n - b[i].first - q[pos - 1].first) * (n - b[i].first - q[pos - 1].first));
}
} else {
ans = min(ans, b[i].second + q[pos].second + (n - b[i].first - q[pos].first) * (n - b[i].first - q[pos].first));
}
}
}
for (int i = 1; i <= tot; i++) {
ans = min(ans, b[i].second + (n - b[i].first) * (n - b[i].first));
}
if(fa != -1 && G[x].size() == 1) dp[x] = sz[x] * sz[x];
a[x] = make_pair(sz[x], dp[x]);
}
int main() {
int x, y;
memset(dp, 0x3f, sizeof(dp));
// freopen("", "r", stdin);
// freopen("", "w", stdout);
scanf("%lld", &n);
for (int i = 1; i < n; i++) {
scanf("%d%d", &x, &y);
add(x, y);
}
ans = 1e18;
dfs(1, -1);
ans = min(ans, dp[1]);
ans -= n;
ans /= 2;
ans = 2ll * n * (n - 1) / 2ll - ans;
printf("%lldn", ans);
}