168902025-05-15 16:45:40BucsMateEnergiatakarékos ellenőrzéscpp17Accepted 100/100128ms14984 KiB
#include <iostream>
#include <vector>
using namespace std;

const int c=1e5+5;

vector<int> adj[c];
long long dp[c][2];
int meret[c];

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

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

int main(){
    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 << dp[1][0] << endl;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms2612 KiB
2Accepted103ms9004 KiB
subtask25/5
3Accepted75ms7340 KiB
4Accepted75ms7360 KiB
5Accepted75ms7636 KiB
6Accepted78ms7340 KiB
7Accepted70ms7224 KiB
subtask315/15
8Accepted3ms2616 KiB
9Accepted3ms2612 KiB
10Accepted3ms2612 KiB
11Accepted3ms2612 KiB
12Accepted3ms2696 KiB
13Accepted3ms2612 KiB
14Accepted3ms2868 KiB
subtask415/15
15Accepted3ms2804 KiB
16Accepted3ms2612 KiB
17Accepted3ms2612 KiB
18Accepted3ms2612 KiB
19Accepted3ms2688 KiB
20Accepted3ms2580 KiB
21Accepted3ms2612 KiB
subtask565/65
22Accepted107ms8860 KiB
23Accepted105ms9012 KiB
24Accepted112ms9044 KiB
25Accepted104ms8904 KiB
26Accepted104ms8960 KiB
27Accepted120ms13920 KiB
28Accepted128ms14984 KiB
29Accepted118ms11316 KiB
30Accepted112ms10140 KiB
31Accepted112ms9120 KiB
32Accepted109ms9012 KiB
33Accepted109ms9020 KiB
34Accepted86ms7640 KiB
35Accepted94ms7728 KiB
36Accepted94ms7632 KiB
37Accepted96ms7892 KiB
38Accepted90ms8240 KiB
39Accepted93ms9392 KiB
40Accepted100ms9276 KiB