49082023-04-06 16:55:10horvathabelEnergiatakarékos ellenőrzéscpp17Wrong answer 0/100103ms27824 KiB
#include <bits/stdc++.h>
using namespace std;
int p[100001];
int t[100001];
bool seen[100001];
int cnt=0; 
int c[100001];
int ans=0; 
vector<int>g[100001];
void dfs(int x){
	if (!seen[x]){
		seen[x]=true; 
		cnt++;
		t[x]=cnt;
		if (c[x]==1 && x!=1){
			int a=x;
			while (c[a]<3 && a!=1){
				a=p[a];
				cnt++;
				ans+=cnt-t[a];
			}
		}
		for (auto edge:g[x]){
			if (!seen[edge]){
				p[edge]=x;
				dfs(edge);
			}
		}
		c[x]=-1;
	}
}
int main() {
	int n;
	cin>>n;
	for (int i=0;i<n-1;i++){
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
		c[a]++;
		c[b]++;

	}

	dfs(1);
	cout<<ans; 
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Wrong answer4ms6672 KiB
2Wrong answer89ms15940 KiB
subtask20/5
3Wrong answer67ms16584 KiB
4Wrong answer68ms16728 KiB
5Wrong answer67ms16944 KiB
6Wrong answer68ms16884 KiB
7Wrong answer67ms17112 KiB
subtask30/15
8Wrong answer4ms7936 KiB
9Wrong answer4ms8232 KiB
10Wrong answer4ms8532 KiB
11Wrong answer4ms8568 KiB
12Wrong answer4ms8612 KiB
13Wrong answer4ms8784 KiB
14Wrong answer4ms8740 KiB
subtask40/15
15Wrong answer4ms8780 KiB
16Wrong answer4ms9028 KiB
17Wrong answer4ms8940 KiB
18Wrong answer4ms9196 KiB
19Wrong answer4ms9152 KiB
20Wrong answer4ms9304 KiB
21Wrong answer4ms9152 KiB
subtask50/65
22Wrong answer90ms18168 KiB
23Wrong answer92ms18124 KiB
24Wrong answer90ms18148 KiB
25Wrong answer90ms18120 KiB
26Wrong answer90ms18152 KiB
27Wrong answer103ms25820 KiB
28Wrong answer101ms27824 KiB
29Wrong answer97ms21976 KiB
30Wrong answer94ms19972 KiB
31Wrong answer93ms18364 KiB
32Wrong answer93ms18264 KiB
33Wrong answer93ms18356 KiB
34Wrong answer82ms18888 KiB
35Wrong answer82ms18888 KiB
36Wrong answer79ms19068 KiB
37Wrong answer85ms19184 KiB
38Wrong answer86ms19192 KiB
39Wrong answer82ms19276 KiB
40Wrong answer86ms19224 KiB