Submission #938230

#TimeUsernameProblemLanguageResultExecution timeMemory
938230weakweakweakPapričice (COCI20_papricice)C++17
110 / 110
169 ms36708 KiB
//抄解,因為我只會暴力,然後往換根dp想一直想不到(我猜根本不能用換根dp解) /* 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], *prev(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), *prev(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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...