1210 2022. 03. 22 21:32:06 ZsofiaKeresztely Energiatakarékos ellenőrzés cpp11 Elfogadva 100/100 112ms 42700 KiB 
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > g;
vector<int> volt;
int outp=0;

void melysegi(int kezdo)
{
  volt[kezdo]=true;
  for (int x : g[kezdo])
  {
    if (!volt[x])
    {
      outp+=4;
      melysegi(x);
      outp+=4;
    }
  }
}

int main(){
  int n, a, b;
  cin>>n;
  g.resize(n+1);
  volt.assign(n+1, false);
  vector<int> zsak;
  for (int i=0; i<n-1; i++)
  {
    cin>>a>>b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  g[1].push_back(1);
  g[1].push_back(1);
  g[1].push_back(1);
  g[1].push_back(1);
  for (int i=2; i<n+1; i++)
  {
    if (g[i].size()==1)
    {
      zsak.push_back(i);
    }
  }
  int szomsz;
  for (int x : zsak)
  {
    volt[x]=true;
    outp+=2;
    szomsz=g[x][0];
    if (g[szomsz].size()==2)
    {
      volt[szomsz]=true;
      outp+=4;
      szomsz = g[szomsz][0]==x ? g[szomsz][1] : g[szomsz][0];
      if (g[szomsz].size()==2)
      {
        outp+=6;
        volt[szomsz]=true;
      }
    }
    else if (g[szomsz].size()==3)
    {
      for (int y : g[szomsz])
      {
        if (y!=x&&g[y].size()==1)
        {
          volt[szomsz]=true;
          outp+=3;
        }
      }
    }
  }
  melysegi(1);
  cout<<outp;
  return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 2ms 1856 KiB
2 Elfogadva 111ms 15564 KiB
subtask2 5/5
3 Elfogadva 71ms 17724 KiB
4 Elfogadva 71ms 18360 KiB
5 Elfogadva 72ms 19260 KiB
6 Elfogadva 68ms 19896 KiB
7 Elfogadva 68ms 20676 KiB
subtask3 15/15
8 Elfogadva 1ms 6900 KiB
9 Elfogadva 1ms 6912 KiB
10 Elfogadva 1ms 6916 KiB
11 Elfogadva 1ms 6912 KiB
12 Elfogadva 1ms 6920 KiB
13 Elfogadva 1ms 6924 KiB
14 Elfogadva 1ms 6932 KiB
subtask4 15/15
15 Elfogadva 1ms 6936 KiB
16 Elfogadva 1ms 6936 KiB
17 Elfogadva 1ms 6940 KiB
18 Elfogadva 1ms 6940 KiB
19 Elfogadva 1ms 6956 KiB
20 Elfogadva 1ms 6956 KiB
21 Elfogadva 1ms 6956 KiB
subtask5 65/65
22 Elfogadva 101ms 20596 KiB
23 Elfogadva 101ms 21756 KiB
24 Elfogadva 104ms 22892 KiB
25 Elfogadva 104ms 24088 KiB
26 Elfogadva 101ms 25268 KiB
27 Elfogadva 112ms 29432 KiB
28 Elfogadva 112ms 31612 KiB
29 Elfogadva 100ms 30216 KiB
30 Elfogadva 100ms 30336 KiB
31 Elfogadva 104ms 30844 KiB
32 Elfogadva 103ms 32056 KiB
33 Elfogadva 103ms 33240 KiB
34 Elfogadva 93ms 35860 KiB
35 Elfogadva 83ms 36964 KiB
36 Elfogadva 89ms 37988 KiB
37 Elfogadva 92ms 39224 KiB
38 Elfogadva 87ms 40576 KiB
39 Elfogadva 85ms 41740 KiB
40 Elfogadva 94ms 42700 KiB