1241 2022. 03. 28 17:50:05 k_balint Energiatakarékos ellenőrzés cpp14 Elfogadva 100/100 79ms 44828 KiB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int c=1e5+5;

vector<int> adj[c];
ll dp[c][2];
int sz[c];

void dfs(int v, int p){
    sz[v]=1;

    for(int x:adj[v]){
        if(x!=p){
            dfs(x,v);
            sz[v]+=sz[x];
            dp[v][0]+=min(dp[x][0]+8, dp[x][1]+2*sz[x]);
            dp[v][1]+=dp[x][1]+2*sz[x];
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n; cin>>n;
    for(int i=1;i<n;i++){
        int a,b; cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    dfs(1,0);

    cout << min(dp[1][0],dp[1][1]) << endl;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 4ms 6604 KiB
2 Elfogadva 79ms 18144 KiB
subtask2 5/5
3 Elfogadva 37ms 16368 KiB
4 Elfogadva 37ms 17124 KiB
5 Elfogadva 35ms 17908 KiB
6 Elfogadva 37ms 18656 KiB
7 Elfogadva 39ms 19444 KiB
subtask3 15/15
8 Elfogadva 3ms 11596 KiB
9 Elfogadva 3ms 11608 KiB
10 Elfogadva 4ms 11608 KiB
11 Elfogadva 3ms 11612 KiB
12 Elfogadva 3ms 11616 KiB
13 Elfogadva 4ms 11616 KiB
14 Elfogadva 3ms 11620 KiB
subtask4 15/15
15 Elfogadva 3ms 11632 KiB
16 Elfogadva 3ms 11628 KiB
17 Elfogadva 3ms 11636 KiB
18 Elfogadva 3ms 11636 KiB
19 Elfogadva 3ms 11648 KiB
20 Elfogadva 4ms 11644 KiB
21 Elfogadva 3ms 11656 KiB
subtask5 65/65
22 Elfogadva 61ms 23264 KiB
23 Elfogadva 75ms 24340 KiB
24 Elfogadva 64ms 25552 KiB
25 Elfogadva 59ms 26708 KiB
26 Elfogadva 59ms 27864 KiB
27 Elfogadva 79ms 38568 KiB
28 Elfogadva 75ms 42268 KiB
29 Elfogadva 68ms 36160 KiB
30 Elfogadva 65ms 34576 KiB
31 Elfogadva 71ms 33740 KiB
32 Elfogadva 67ms 34612 KiB
33 Elfogadva 63ms 35756 KiB
34 Elfogadva 39ms 34536 KiB
35 Elfogadva 41ms 35704 KiB
36 Elfogadva 41ms 36944 KiB
37 Elfogadva 54ms 38340 KiB
38 Elfogadva 56ms 40160 KiB
39 Elfogadva 54ms 43504 KiB
40 Elfogadva 54ms 44828 KiB