187532025-11-04 12:12:10algoproFire on a Treecpp17Accepted 100/100560ms75620 KiB
// UUID: 418a536e-96c5-4373-ba35-94f610e22692
// @check-accepted: examples cubic quadratic all
#include <fstream>
#include <iostream>
#include <set>
#include <vector>
using namespace std;
vector<int> v[200005];
vector<int> ans(200005);
multiset<int> q[200005];
int sum[200005];
int ma[200005];
int dfs(int pos, int prec) {
    int m = 0;
    int tot = 0;
    for (int x : v[pos]) {
        if (x == prec) continue;
        int k = dfs(x, pos);
        tot += k;
        m = max(m, k);
        q[pos].insert(k);
    }
    sum[pos] = tot + 1;
    ma[pos] = m;
    q[pos].insert(0);
    q[pos].insert(0);
    return tot - m + 1;
}
void reroot(int pos, int prec) {
    ans[pos] = sum[pos] - ma[pos];

    for (int x : v[pos]) {
        if (x == prec) continue;
        sum[pos] -= (sum[x] - ma[x]);
        q[pos].erase(q[pos].find(sum[x] - ma[x]));
        ma[pos] = *prev(q[pos].end());
        sum[x] += sum[pos] - ma[pos];
        q[x].insert(sum[pos] - ma[pos]);
        ma[x] = *prev(q[x].end());

        reroot(x, pos);

        sum[x] -= sum[pos] - ma[pos];
        q[x].erase(q[x].find(sum[pos] - ma[pos]));
        ma[x] = *prev(q[x].end());
        sum[pos] += (sum[x] - ma[x]);
        q[pos].insert(sum[x] - ma[x]);
        ma[pos] = *prev(q[pos].end());
    }
}

int main() {
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for (int i = 0, a, b; i < N - 1; i++) {
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(0, -1);
    reroot(0, -1);
    for (int i = 0; i < N; i++) cout << ans[i] << " ";
    cout << '\n';
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted16ms15156 KiB
2Accepted13ms15156 KiB
subtask235/35
3Accepted17ms15156 KiB
4Accepted13ms15156 KiB
5Accepted13ms15112 KiB
6Accepted17ms15240 KiB
7Accepted13ms15160 KiB
subtask325/25
8Accepted17ms15280 KiB
9Accepted14ms15436 KiB
10Accepted17ms15892 KiB
11Accepted14ms15640 KiB
12Accepted17ms15668 KiB
13Accepted14ms15476 KiB
subtask440/40
14Accepted287ms37880 KiB
15Accepted331ms45912 KiB
16Accepted354ms75620 KiB
17Accepted560ms54576 KiB
18Accepted370ms51760 KiB
19Accepted527ms54068 KiB
20Accepted416ms54444 KiB
21Accepted518ms54324 KiB
22Accepted377ms54248 KiB