187862025-11-04 18:12:47algoproFire on a Treecpp17Accepted 100/100330ms35124 KiB
// UUID: 590964de-e9dc-40c1-a136-e940757561a6
#include <bits/stdc++.h>
using namespace std;

void dfs1(int i, int l, vector<vector<int>> & g, vector<int> & x) {
    int maxi = 0, sum = 1;
    for (int j : g[i]) {
        if (j == l) continue;
        dfs1(j, i, g, x);
        maxi = max(maxi, x[j]);
        sum += x[j];
    }

    x[i] = sum - maxi;
}

void dfs2(int i, int l, vector<vector<int>> & g, vector<int> & x, vector<int> & y, vector<int> & z) {
	int max1 = 200000, max2 = 200000, sum = 1 + y[i];
    for (int j : g[i]) {
        if (j == l) continue;
        if (x[j] > x[max1]) {
            max2 = max1;
            max1 = j;
        } else if (x[j] > x[max2]) max2 = j;
        sum += x[j];
    }

	z[i] = sum - max(x[max1], y[i]);

    for (int j : g[i]) {
        if (j == l) continue;
		int maxi = x[max1];
		if (j == max1) maxi = x[max2];
		if (y[i] > maxi) maxi = y[i];
		y[j] = sum - maxi - x[j];
        dfs2(j, i, g, x, y, z);
	}

}

int main() {
	int n;
    cin >> n;
    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    vector<int> x(200001), y(n), z(n);
    dfs1(0, -1, g, x);
    dfs2(0, -1, g, x, y, z);
	for (int a : z) cout << a << " ";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms1076 KiB
2Accepted2ms1076 KiB
subtask235/35
3Accepted2ms1076 KiB
4Accepted2ms1076 KiB
5Accepted2ms1076 KiB
6Accepted2ms1076 KiB
7Accepted2ms1076 KiB
subtask325/25
8Accepted2ms1140 KiB
9Accepted3ms1116 KiB
10Accepted3ms1332 KiB
11Accepted3ms1076 KiB
12Accepted4ms1076 KiB
13Accepted3ms1076 KiB
subtask440/40
14Accepted142ms8712 KiB
15Accepted181ms11388 KiB
16Accepted263ms35124 KiB
17Accepted289ms14424 KiB
18Accepted296ms13108 KiB
19Accepted268ms13876 KiB
20Accepted259ms14348 KiB
21Accepted330ms14132 KiB
22Accepted307ms13876 KiB