187742025-11-04 17:46:34algoproFire on a Treecpp17Wrong answer 0/100425ms42160 KiB
// UUID: 5b5ea352-8557-4448-8056-78c40a40e783
#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];
                } else {
                    dpv[v].push_back(dpv[u][1]);
                    dpvsum[v]+=dpv[u][1];
                }
            }
        } 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
subtask20/35
3Wrong answer1ms316 KiB
4Accepted1ms316 KiB
5Accepted1ms316 KiB
6Wrong answer1ms512 KiB
7Wrong answer1ms316 KiB
subtask30/25
8Wrong answer1ms500 KiB
9Wrong answer3ms564 KiB
10Accepted3ms820 KiB
11Wrong answer3ms564 KiB
12Wrong answer3ms564 KiB
13Wrong answer3ms564 KiB
subtask40/40
14Wrong answer190ms14756 KiB
15Wrong answer284ms20332 KiB
16Accepted347ms42160 KiB
17Wrong answer319ms25900 KiB
18Wrong answer301ms23460 KiB
19Wrong answer337ms24884 KiB
20Wrong answer384ms25908 KiB
21Wrong answer425ms25292 KiB
22Wrong answer319ms24884 KiB