187792025-11-04 17:57:42CzDaniFire on a Treecpp17Accepted 100/100395ms45080 KiB
#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<vector<int>> adj, dpv;
vector<int> ledp, dp, dpvsum;

void dfs1(int v, int p) {
    int maxi = 0;
    for (int u : adj[v]) {
        if (u==p)continue;
        dfs1(u, v);
        maxi=max(maxi, ledp[u]);
        ledp[v]+=ledp[u];
    }
    ledp[v]++;
    ledp[v]-=maxi;
    return;
}

void dfs2(int v, int p) {
    dpvsum[v]++;
    for (int u : adj[v]) {
        if (u==p) {
            if (adj[u].size()<=2) {
                dpv[v].push_back(1);
                dpvsum[v]++;
            } else {
                if (dpv[u][0]==ledp[v]||dpv[u][1]==ledp[v]) {
                    // dpv[v].push_back(dpv[u][2]);
                    // dpvsum[v]+=dpv[u][2];
                    dpv[v].push_back(dpvsum[u]-dpv[u][0]-dpv[u][1]);
                    dpvsum[v]+=dpvsum[u]-dpv[u][0]-dpv[u][1];
                } else {
                    // dpv[v].push_back(dpv[u][1]);
                    // dpvsum[v]+=dpv[u][1];
                    dpv[v].push_back(dpvsum[u]-dpv[u][0]-ledp[v]);
                    dpvsum[v]+=dpvsum[u]-dpv[u][0]-ledp[v];
                }
            }
        } else {
            dpv[v].push_back(ledp[u]);
            dpvsum[v]+=ledp[u];
        }
    }
    sort(dpv[v].rbegin(), dpv[v].rend());
    dp[v]=dpvsum[v]-dpv[v][0];
    for (int u : adj[v]) {
        if (u==p)continue;
        dfs2(u, v);
    }
}

int main() {
    cin >> n;
    adj.assign(n+1, {});
    dpv.assign(n+1, {});
    dp.assign(n+1, 0);
    ledp.assign(n+1, 0);
    dpvsum.assign(n+1, 0);
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        adj[a+1].push_back(b+1);
        adj[b+1].push_back(a+1);
    }
    dfs1(2, 0);
    dfs2(2, 0);
    for (int i = 1; i <= n; i++)cout<<dp[i]<<' ';
    cout<<'\n';

}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Accepted1ms316 KiB
subtask235/35
3Accepted1ms316 KiB
4Accepted1ms316 KiB
5Accepted1ms316 KiB
6Accepted1ms316 KiB
7Accepted1ms316 KiB
subtask325/25
8Accepted1ms316 KiB
9Accepted2ms564 KiB
10Accepted3ms732 KiB
11Accepted3ms564 KiB
12Accepted3ms536 KiB
13Accepted3ms564 KiB
subtask440/40
14Accepted180ms14804 KiB
15Accepted226ms20272 KiB
16Accepted287ms45080 KiB
17Accepted375ms25908 KiB
18Accepted370ms23604 KiB
19Accepted328ms24884 KiB
20Accepted314ms25904 KiB
21Accepted395ms25396 KiB
22Accepted300ms24880 KiB