Submission #938231

#	Time	Username	Problem	Language	Result	Execution time	Memory
938231		weakweakweak	Papričice (COCI20_papricice)	C++17	110 / 110	164 ms	34048 KiB

papricice

//抄解，因為我只會暴力，然後往換根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 - *--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;}

• Subtask 1: 15 / 15
• Subtask 2: 35 / 35
• Subtask 3: 60 / 60