187752025-11-04 17:47:59algoproFire on a Treecpp17Időlimit túllépés 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) << " ";
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva1ms508 KiB
subtask235/35
3Elfogadva1ms316 KiB
4Elfogadva1ms432 KiB
5Elfogadva1ms316 KiB
6Elfogadva1ms316 KiB
7Elfogadva1ms316 KiB
subtask325/25
8Elfogadva13ms524 KiB
9Elfogadva4ms564 KiB
10Elfogadva4ms1084 KiB
11Elfogadva250ms672 KiB
12Elfogadva7ms884 KiB
13Elfogadva6ms820 KiB
subtask40/40
14Elfogadva813ms29500 KiB
15Időlimit túllépés1.088s19636 KiB
16Elfogadva578ms66876 KiB
17Időlimit túllépés1.088s25000 KiB
18Időlimit túllépés1.088s47924 KiB
19Időlimit túllépés1.088s43316 KiB
20Időlimit túllépés1.083s25000 KiB
21Időlimit túllépés1.087s39732 KiB
22Időlimit túllépés1.087s49460 KiB