//抄解，因為我只會暴力，然後往換根dp想一直想不到(我猜根本不能用換根dp解)
//我根本就不會iterator
/*
case 1. y is x's ancenstor
有sz[x], sz[y] - sz[x], n - sz[y] 3塊。
無論，誰是最小，我都會希望除了sz[x]以外的兩塊盡量接近。
我們想要abs(sz[y] - sz[x] - (n - sz[u])) = abs(2sz[y] - (n + sz[x])) = 2abs(sz[y] - (n + sz[x]) / 2) 盡量小。
也就等同於想要sz[y]盡量接近(n + sz[x]) / 2
case 2. y isn't x's ancenstor
有sz[x], sz[y], n - sz[x] - sz[y] 3塊
相同的我們希望sz[y]和n - sz[y] - sz[x]盡量接近。
我們想要abs((n - sz[y] - sz[x]) - sz[y]) 盡量小
等同於想要sz[y] 盡量接近(n - sz[x]) / 2
這個case比較顯然一點
*/
#include <bits/stdc++.h>
using namespace std;
multiset<int> anc, nanc;
int n, sz[510000], ans = 10010000;
vector <int> e[510000];
void dfs (int i, int par) {
sz[i] = 1;
for (int j : e[i]) if (j != par) {
dfs(j, i);
sz[i] += sz[j];
}
return;}
int get (int x, int y, int z) {
int mn = min({x, y, z}), mx = max({x, y, z});
if (mn <= 0) return INT_MAX;
return mx - mn;
}
void dfs2 (int i, int par) {
if (anc . size()) {
auto it = anc.upper_bound((n + sz[i]) / 2);
if (it != anc.end()) ans = min(ans, get(n - *it, sz[i], *it - sz[i]));
if (it != anc.begin()) ans = min(ans, get(n - *prev(it), sz[i], *--(it) - sz[i]));
}
if (nanc . size()) {
auto it = nanc.upper_bound((n - sz[i]) / 2);
if (it != nanc.end()) ans = min(ans, get(n - sz[i] - *it, *it, sz[i]));
if (it != nanc.begin()) ans = min(ans, get(n - sz[i] - *prev(it), *--(it), sz[i]));
}
anc . insert(sz[i]);
for (int j : e[i]) if (j != par) dfs2(j, i);
nanc . insert(sz[i]);
anc . erase(sz[i]);
}
signed main () {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n;
for (int i = 2, x, y; i <= n; i++) {
cin >> x >> y;
e[x] . push_back(y);
e[y] . push_back(x);
}
dfs(1, 1);
dfs2(1, 1);
cout << ans << '\n';
return 0;}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
12892 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
12892 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
12892 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
