12092022-03-22 20:56:25Zoli9Energiatakarékos ellenőrzéscpp11Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva4ms6616 KiB
2Elfogadva71ms19116 KiB
subtask25/5
3Elfogadva41ms17364 KiB
4Elfogadva43ms18116 KiB
5Elfogadva43ms18904 KiB
6Elfogadva41ms19528 KiB
7Elfogadva43ms20440 KiB
subtask315/15
8Elfogadva3ms11612 KiB
9Elfogadva3ms11616 KiB
10Elfogadva3ms11616 KiB
11Elfogadva4ms11624 KiB
12Elfogadva3ms11628 KiB
13Elfogadva3ms11636 KiB
14Elfogadva3ms11640 KiB
subtask415/15
15Elfogadva4ms11640 KiB
16Elfogadva3ms11644 KiB
17Elfogadva3ms11648 KiB
18Elfogadva4ms11648 KiB
19Elfogadva3ms11656 KiB
20Elfogadva3ms11660 KiB
21Elfogadva3ms11664 KiB
subtask565/65
22Elfogadva64ms24248 KiB
23Elfogadva68ms25408 KiB
24Elfogadva61ms26556 KiB
25Elfogadva63ms27716 KiB
26Elfogadva70ms28868 KiB
27Elfogadva86ms39572 KiB
28Elfogadva87ms43272 KiB
29Elfogadva76ms37144 KiB
30Elfogadva90ms35568 KiB
31Elfogadva67ms34680 KiB
32Elfogadva75ms35672 KiB
33Elfogadva65ms36760 KiB
34Elfogadva41ms35532 KiB
35Elfogadva43ms36700 KiB
36Elfogadva46ms37856 KiB
37Elfogadva46ms39352 KiB
38Elfogadva52ms41716 KiB
39Elfogadva52ms44724 KiB
40Elfogadva57ms45828 KiB