49082023-04-06 16:55:10horvathabelEnergiatakarékos ellenőrzéscpp17Hibás válasz 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; 
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Hibás válasz4ms6672 KiB
2Hibás válasz89ms15940 KiB
subtask20/5
3Hibás válasz67ms16584 KiB
4Hibás válasz68ms16728 KiB
5Hibás válasz67ms16944 KiB
6Hibás válasz68ms16884 KiB
7Hibás válasz67ms17112 KiB
subtask30/15
8Hibás válasz4ms7936 KiB
9Hibás válasz4ms8232 KiB
10Hibás válasz4ms8532 KiB
11Hibás válasz4ms8568 KiB
12Hibás válasz4ms8612 KiB
13Hibás válasz4ms8784 KiB
14Hibás válasz4ms8740 KiB
subtask40/15
15Hibás válasz4ms8780 KiB
16Hibás válasz4ms9028 KiB
17Hibás válasz4ms8940 KiB
18Hibás válasz4ms9196 KiB
19Hibás válasz4ms9152 KiB
20Hibás válasz4ms9304 KiB
21Hibás válasz4ms9152 KiB
subtask50/65
22Hibás válasz90ms18168 KiB
23Hibás válasz92ms18124 KiB
24Hibás válasz90ms18148 KiB
25Hibás válasz90ms18120 KiB
26Hibás válasz90ms18152 KiB
27Hibás válasz103ms25820 KiB
28Hibás válasz101ms27824 KiB
29Hibás válasz97ms21976 KiB
30Hibás válasz94ms19972 KiB
31Hibás válasz93ms18364 KiB
32Hibás válasz93ms18264 KiB
33Hibás válasz93ms18356 KiB
34Hibás válasz82ms18888 KiB
35Hibás válasz82ms18888 KiB
36Hibás válasz79ms19068 KiB
37Hibás válasz85ms19184 KiB
38Hibás válasz86ms19192 KiB
39Hibás válasz82ms19276 KiB
40Hibás válasz86ms19224 KiB