1242 2022. 03. 28 18:01:04 Valaki2 Energiatakarékos ellenőrzés cpp14 Elfogadva 100/100 90ms 48536 KiB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second

const int maxn = 1e5;

int n;
vector<int> g[maxn + 1];
int ans[maxn + 1];
int full[maxn + 1];
int par[maxn + 1];
int subtree_size[maxn + 1];

void dfs(int cur, int parent) {
    par[cur] = parent;
    for(int nei : g[cur]) {
        if(nei != parent) {
            dfs(nei, cur);
            subtree_size[cur] += subtree_size[nei];
            full[cur] += full[nei];
            ans[cur] += min(8 + ans[nei], 2 * subtree_size[nei] + full[nei]);
        }
    }
    subtree_size[cur]++;
    full[cur] += (subtree_size[cur] - 1) * 2;
}

void solve() {
    cin >> n;
    for(int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }
    dfs(1, 0);
    cout << ans[1] << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 4ms 6644 KiB
2 Elfogadva 86ms 21580 KiB
subtask2 5/5
3 Elfogadva 46ms 20916 KiB
4 Elfogadva 48ms 21660 KiB
5 Elfogadva 48ms 22520 KiB
6 Elfogadva 48ms 23192 KiB
7 Elfogadva 48ms 23932 KiB
subtask3 15/15
8 Elfogadva 3ms 11720 KiB
9 Elfogadva 3ms 11728 KiB
10 Elfogadva 3ms 11728 KiB
11 Elfogadva 3ms 11724 KiB
12 Elfogadva 4ms 11728 KiB
13 Elfogadva 4ms 11748 KiB
14 Elfogadva 3ms 11752 KiB
subtask4 15/15
15 Elfogadva 3ms 11740 KiB
16 Elfogadva 3ms 11752 KiB
17 Elfogadva 3ms 11748 KiB
18 Elfogadva 3ms 11768 KiB
19 Elfogadva 3ms 11756 KiB
20 Elfogadva 3ms 11776 KiB
21 Elfogadva 3ms 11764 KiB
subtask5 65/65
22 Elfogadva 75ms 26656 KiB
23 Elfogadva 79ms 27804 KiB
24 Elfogadva 83ms 28956 KiB
25 Elfogadva 78ms 30108 KiB
26 Elfogadva 74ms 31284 KiB
27 Elfogadva 86ms 41048 KiB
28 Elfogadva 90ms 44732 KiB
29 Elfogadva 89ms 39532 KiB
30 Elfogadva 78ms 38016 KiB
31 Elfogadva 79ms 37100 KiB
32 Elfogadva 89ms 38052 KiB
33 Elfogadva 79ms 39180 KiB
34 Elfogadva 52ms 39192 KiB
35 Elfogadva 50ms 40256 KiB
36 Elfogadva 48ms 41540 KiB
37 Elfogadva 52ms 43124 KiB
38 Elfogadva 54ms 44896 KiB
39 Elfogadva 68ms 47192 KiB
40 Elfogadva 64ms 48536 KiB