187752025-11-04 17:47:59algoproFire on a Treecpp17Time limit exceeded 60/1001.088s66876 KiB
// UUID: 14689821-380c-4c73-a87e-70acab557ef1
#include <bits/stdc++.h>
using namespace std;
#define int long long



signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<vector<int>>adj(n);
    for(int i = 1; i < n; i++){
        int a,b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    map<pair<int,int>, int>cache;

    function<int(int,int)> dfs;
    dfs = [&](int cs, int p){
        if(cache.count({cs,p}))return cache [{cs,p}];
        int sum = 0, ln = 0;
        for(int i : adj[cs]){
            if(i != p){
                int res = dfs(i, cs);
                sum += res;
                ln = max(ln, res);
            }
        }
        return cache[{cs,p}] = sum - ln +1;
    };

    for(int i = 0; i < n; i++){
        cout << dfs(i, -1) << " ";
    }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Accepted1ms508 KiB
subtask235/35
3Accepted1ms316 KiB
4Accepted1ms432 KiB
5Accepted1ms316 KiB
6Accepted1ms316 KiB
7Accepted1ms316 KiB
subtask325/25
8Accepted13ms524 KiB
9Accepted4ms564 KiB
10Accepted4ms1084 KiB
11Accepted250ms672 KiB
12Accepted7ms884 KiB
13Accepted6ms820 KiB
subtask40/40
14Accepted813ms29500 KiB
15Time limit exceeded1.088s19636 KiB
16Accepted578ms66876 KiB
17Time limit exceeded1.088s25000 KiB
18Time limit exceeded1.088s47924 KiB
19Time limit exceeded1.088s43316 KiB
20Time limit exceeded1.083s25000 KiB
21Time limit exceeded1.087s39732 KiB
22Time limit exceeded1.087s49460 KiB