12092022-03-22 20:56:25Zoli9Energiatakarékos ellenőrzéscpp11Accepted 100/10090ms45828 KiB
#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> G[100009];
bool b[100009];
long long ans_greedy[100009];
long long ans[100009];
long long children[100009];
void dfs(int x)
{
    b[x]=true;
    children[x]=1;
    for(int nb: G[x])
    {
        if(!b[nb])
        {
            dfs(nb);
            children[x]+=children[nb];
            ans_greedy[x]+=(2*children[nb]+ans_greedy[nb]);
            ans[x]+=min(2*children[nb]+ans_greedy[nb], 8+ans[nb]);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1; i<n; i++)
    {
        int a, b;
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(1);
    cout<<ans[1]<<'\n';
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted4ms6616 KiB
2Accepted71ms19116 KiB
subtask25/5
3Accepted41ms17364 KiB
4Accepted43ms18116 KiB
5Accepted43ms18904 KiB
6Accepted41ms19528 KiB
7Accepted43ms20440 KiB
subtask315/15
8Accepted3ms11612 KiB
9Accepted3ms11616 KiB
10Accepted3ms11616 KiB
11Accepted4ms11624 KiB
12Accepted3ms11628 KiB
13Accepted3ms11636 KiB
14Accepted3ms11640 KiB
subtask415/15
15Accepted4ms11640 KiB
16Accepted3ms11644 KiB
17Accepted3ms11648 KiB
18Accepted4ms11648 KiB
19Accepted3ms11656 KiB
20Accepted3ms11660 KiB
21Accepted3ms11664 KiB
subtask565/65
22Accepted64ms24248 KiB
23Accepted68ms25408 KiB
24Accepted61ms26556 KiB
25Accepted63ms27716 KiB
26Accepted70ms28868 KiB
27Accepted86ms39572 KiB
28Accepted87ms43272 KiB
29Accepted76ms37144 KiB
30Accepted90ms35568 KiB
31Accepted67ms34680 KiB
32Accepted75ms35672 KiB
33Accepted65ms36760 KiB
34Accepted41ms35532 KiB
35Accepted43ms36700 KiB
36Accepted46ms37856 KiB
37Accepted46ms39352 KiB
38Accepted52ms41716 KiB
39Accepted52ms44724 KiB
40Accepted57ms45828 KiB