10077 2024. 03. 26 16:18:20 111 Energiatakarékos ellenőrzés cpp17 Elfogadva 100/100 71ms 56572 KiB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
#ifndef ONLINE_JUDGE
	freopen("be1.txt","r",stdin);
#endif
	int N;
	cin>>N;
	vector<vector<int>>g(N+1);
	for(int i=0;i<N-1;i++){
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	vector<int>s(N+1),a(N+1),b(N+1),c(N+1);
	auto dfs=[&](auto self,int i)->void{
		s[i]=1;
		for(int j:g[i]){
			if(s[j]){
				continue;
			}
			self(self,j);
			s[i]+=s[j];
			c[i]+=c[j];
			int x=b[j]+s[j]*2+c[j];
			int y=a[j]+8;
			if(y<x){
				a[i]+=y;
				c[i]+=4;
			}
			else{
				a[i]+=x;
			}
			b[i]+=min(x,y);
		}
	};
	dfs(dfs,1);
	cout<<a[1]<<'\n';
	return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1956 KiB
2 Elfogadva 59ms 21484 KiB
subtask2 5/5
3 Elfogadva 41ms 22688 KiB
4 Elfogadva 41ms 23676 KiB
5 Elfogadva 41ms 24504 KiB
6 Elfogadva 41ms 25396 KiB
7 Elfogadva 41ms 26400 KiB
subtask3 15/15
8 Elfogadva 3ms 8016 KiB
9 Elfogadva 3ms 7944 KiB
10 Elfogadva 3ms 7948 KiB
11 Elfogadva 2ms 7916 KiB
12 Elfogadva 2ms 7956 KiB
13 Elfogadva 3ms 7960 KiB
14 Elfogadva 3ms 8188 KiB
subtask4 15/15
15 Elfogadva 2ms 8180 KiB
16 Elfogadva 3ms 8312 KiB
17 Elfogadva 2ms 8396 KiB
18 Elfogadva 3ms 8528 KiB
19 Elfogadva 3ms 8620 KiB
20 Elfogadva 3ms 8620 KiB
21 Elfogadva 3ms 8624 KiB
subtask5 65/65
22 Elfogadva 57ms 28020 KiB
23 Elfogadva 57ms 29196 KiB
24 Elfogadva 61ms 30660 KiB
25 Elfogadva 61ms 32044 KiB
26 Elfogadva 57ms 33216 KiB
27 Elfogadva 70ms 50872 KiB
28 Elfogadva 71ms 56572 KiB
29 Elfogadva 65ms 45416 KiB
30 Elfogadva 68ms 42016 KiB
31 Elfogadva 64ms 39756 KiB
32 Elfogadva 61ms 40492 KiB
33 Elfogadva 61ms 41532 KiB
34 Elfogadva 50ms 43292 KiB
35 Elfogadva 46ms 44428 KiB
36 Elfogadva 46ms 45604 KiB
37 Elfogadva 50ms 47432 KiB
38 Elfogadva 52ms 48836 KiB
39 Elfogadva 56ms 49956 KiB
40 Elfogadva 54ms 51244 KiB