Submission #5,009

2023-04-09 11:03:37

cpp11

Accepted 100/100

133ms

35052 KiB

#include <bits/stdc++.h> 
#define MAXN 101000
using namespace std;
int n,p[MAXN],dp[MAXN],sub[MAXN];
vector<int>s[MAXN];
vector<int>c[MAXN];
void dfs(int v)
{
	for(int k:s[v])
	{
		if(p[v]!=k)
		{
			p[k]=v;
			dfs(k);
			sub[v]+=sub[k]+1;
			dp[v]+=min(dp[k]+(sub[k]+1)*2,dp[k]+8);
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int a,b;
		cin>>a>>b;
		s[a].push_back(b);
		s[b].push_back(a);
	}
	dfs(1);
	cout<<dp[1]<<'\n';
    return 0;
}

	Sum	Test	Verdict	Time	Memory
subtask1	0/0
		1	Accepted	6ms	11360 KiB
		2	Accepted	97ms	20612 KiB
subtask2	5/5
		3	Accepted	71ms	19480 KiB
		4	Accepted	70ms	19692 KiB
		5	Accepted	74ms	19976 KiB
		6	Accepted	74ms	19816 KiB
		7	Accepted	71ms	20180 KiB
subtask3	15/15
		8	Accepted	6ms	12620 KiB
		9	Accepted	6ms	12652 KiB
		10	Accepted	6ms	12876 KiB
		11	Accepted	7ms	13088 KiB
		12	Accepted	6ms	13072 KiB
		13	Accepted	6ms	13204 KiB
		14	Accepted	6ms	13416 KiB
subtask4	15/15
		15	Accepted	6ms	13428 KiB
		16	Accepted	6ms	13552 KiB
		17	Accepted	6ms	13788 KiB
		18	Accepted	6ms	13640 KiB
		19	Accepted	6ms	13644 KiB
		20	Accepted	6ms	13744 KiB
		21	Accepted	6ms	13796 KiB
subtask5	65/65
		22	Accepted	94ms	22552 KiB
		23	Accepted	114ms	22576 KiB
		24	Accepted	118ms	22596 KiB
		25	Accepted	94ms	22548 KiB
		26	Accepted	93ms	22804 KiB
		27	Accepted	101ms	32584 KiB
		28	Accepted	133ms	35052 KiB
		29	Accepted	101ms	27920 KiB
		30	Accepted	97ms	25260 KiB
		31	Accepted	94ms	23080 KiB
		32	Accepted	94ms	23112 KiB
		33	Accepted	94ms	23112 KiB
		34	Accepted	86ms	22388 KiB
		35	Accepted	89ms	22476 KiB
		36	Accepted	86ms	22584 KiB
		37	Accepted	92ms	22932 KiB
		38	Accepted	92ms	23664 KiB
		39	Accepted	90ms	24360 KiB
		40	Accepted	93ms	24280 KiB