49072023-04-06 16:54:50horvathabelEnergiatakarékos ellenőrzéspython3Futási hiba 0/10017ms13764 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
1Futási hiba17ms10740 KiB
2Futási hiba17ms10992 KiB
subtask20/5
3Futási hiba17ms11228 KiB
4Futási hiba17ms11464 KiB
5Futási hiba17ms11488 KiB
6Futási hiba17ms11448 KiB
7Futási hiba17ms11736 KiB
subtask30/15
8Futási hiba17ms11828 KiB
9Futási hiba17ms11840 KiB
10Futási hiba17ms12316 KiB
11Futási hiba17ms12336 KiB
12Futási hiba16ms12344 KiB
13Futási hiba17ms12404 KiB
14Futási hiba17ms12424 KiB
subtask40/15
15Futási hiba16ms12532 KiB
16Futási hiba17ms12748 KiB
17Futási hiba17ms12508 KiB
18Futási hiba17ms12544 KiB
19Futási hiba17ms12756 KiB
20Futási hiba17ms12948 KiB
21Futási hiba17ms12808 KiB
subtask50/65
22Futási hiba17ms12512 KiB
23Futási hiba17ms12976 KiB
24Futási hiba17ms12992 KiB
25Futási hiba17ms13088 KiB
26Futási hiba17ms13304 KiB
27Futási hiba17ms13288 KiB
28Futási hiba17ms13444 KiB
29Futási hiba17ms13216 KiB
30Futási hiba17ms13256 KiB
31Futási hiba17ms13300 KiB
32Futási hiba17ms13200 KiB
33Futási hiba17ms13184 KiB
34Futási hiba17ms13196 KiB
35Futási hiba17ms12972 KiB
36Futási hiba17ms13372 KiB
37Futási hiba17ms13484 KiB
38Futási hiba17ms13652 KiB
39Futási hiba17ms13764 KiB
40Futási hiba17ms13752 KiB