187852025-11-04 18:10:50algoproFire on a Treecpp17Hibás válasz 0/100328ms35192 KiB
// UUID: 9f182b31-2d46-4c91-afd7-85686188c4b3
#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;
        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 << " ";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva2ms1320 KiB
2Elfogadva1ms1076 KiB
subtask20/35
3Hibás válasz2ms1076 KiB
4Hibás válasz2ms1080 KiB
5Elfogadva2ms1076 KiB
6Hibás válasz2ms1076 KiB
7Hibás válasz1ms1076 KiB
subtask30/25
8Hibás válasz2ms1076 KiB
9Hibás válasz3ms1076 KiB
10Elfogadva4ms1332 KiB
11Hibás válasz4ms1076 KiB
12Hibás válasz3ms1076 KiB
13Hibás válasz3ms1076 KiB
subtask40/40
14Hibás válasz152ms8836 KiB
15Hibás válasz216ms11536 KiB
16Elfogadva317ms35192 KiB
17Hibás válasz263ms14428 KiB
18Hibás válasz300ms13108 KiB
19Hibás válasz296ms14072 KiB
20Hibás válasz266ms14552 KiB
21Hibás válasz328ms14288 KiB
22Hibás válasz300ms13876 KiB