Submission #48555799

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll MOD=998244353;
// head
const int N=3e5+5;
vector<vector<int>> G(N);
int dfs(int now,int fa)
{
	if(G[now].size()==1) return 1;
	int ans=0;
	for(auto it:G[now]){
		if(fa!=it) ans+=dfs(it,now);
	}
	return ans+1;
}
signed main() 
{
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	
	int n;cin>>n;
	for(int i=0;i<n-1;i++){
		int u,v;cin>>u>>v;
		--u,--v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	if(G[0].size()==1) {cout<<1<<endl;return 0;}
	int ans=0,sum=0;
	for(auto it:G[0]){
		int tmp=dfs(it,0);
		sum+=tmp,ans=max(ans,tmp);
	}
	cout<<sum-ans+1<<endl;
}

Submission Info

Submission Time
Task D - Erase Leaves
User gangbengr
Language C++ 20 (gcc 12.2)
Score 400
Code Size 901 Byte
Status AC
Exec Time 186 ms
Memory 33356 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 49
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt, 01_random_30.txt, 01_random_31.txt, 01_random_32.txt, 01_random_33.txt, 01_random_34.txt, 01_random_35.txt, 01_random_36.txt, 01_random_37.txt, 01_random_38.txt, 01_random_39.txt, 01_random_40.txt, 01_random_41.txt, 01_random_42.txt, 01_random_43.txt, 01_random_44.txt, 01_random_45.txt, 01_random_46.txt, 01_random_47.txt, 01_random_48.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 4 ms 9920 KiB
00_sample_01.txt AC 4 ms 10012 KiB
00_sample_02.txt AC 4 ms 10064 KiB
01_random_03.txt AC 74 ms 22412 KiB
01_random_04.txt AC 96 ms 19436 KiB
01_random_05.txt AC 119 ms 22868 KiB
01_random_06.txt AC 75 ms 22464 KiB
01_random_07.txt AC 97 ms 19452 KiB
01_random_08.txt AC 124 ms 22704 KiB
01_random_09.txt AC 78 ms 22444 KiB
01_random_10.txt AC 172 ms 27688 KiB
01_random_11.txt AC 116 ms 22944 KiB
01_random_12.txt AC 113 ms 21200 KiB
01_random_13.txt AC 82 ms 22576 KiB
01_random_14.txt AC 186 ms 31316 KiB
01_random_15.txt AC 122 ms 22864 KiB
01_random_16.txt AC 123 ms 21352 KiB
01_random_17.txt AC 85 ms 22524 KiB
01_random_18.txt AC 180 ms 29204 KiB
01_random_19.txt AC 131 ms 22788 KiB
01_random_20.txt AC 106 ms 21280 KiB
01_random_21.txt AC 81 ms 22528 KiB
01_random_22.txt AC 180 ms 33356 KiB
01_random_23.txt AC 126 ms 22784 KiB
01_random_24.txt AC 132 ms 21352 KiB
01_random_25.txt AC 14 ms 12316 KiB
01_random_26.txt AC 14 ms 11784 KiB
01_random_27.txt AC 62 ms 17288 KiB
01_random_28.txt AC 15 ms 12044 KiB
01_random_29.txt AC 60 ms 19844 KiB
01_random_30.txt AC 108 ms 19108 KiB
01_random_31.txt AC 106 ms 19976 KiB
01_random_32.txt AC 57 ms 18524 KiB
01_random_33.txt AC 38 ms 13628 KiB
01_random_34.txt AC 125 ms 22540 KiB
01_random_35.txt AC 10 ms 11056 KiB
01_random_36.txt AC 13 ms 12304 KiB
01_random_37.txt AC 33 ms 14232 KiB
01_random_38.txt AC 6 ms 10396 KiB
01_random_39.txt AC 85 ms 21848 KiB
01_random_40.txt AC 170 ms 26524 KiB
01_random_41.txt AC 128 ms 23140 KiB
01_random_42.txt AC 123 ms 21196 KiB
01_random_43.txt AC 77 ms 21832 KiB
01_random_44.txt AC 169 ms 26572 KiB
01_random_45.txt AC 120 ms 22828 KiB
01_random_46.txt AC 126 ms 21216 KiB
01_random_47.txt AC 4 ms 10080 KiB
01_random_48.txt AC 5 ms 10004 KiB