49072023-04-06 16:54:50horvathabelEnergiatakarékos ellenőrzéspython3Runtime error 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; 
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Runtime error17ms10740 KiB
2Runtime error17ms10992 KiB
subtask20/5
3Runtime error17ms11228 KiB
4Runtime error17ms11464 KiB
5Runtime error17ms11488 KiB
6Runtime error17ms11448 KiB
7Runtime error17ms11736 KiB
subtask30/15
8Runtime error17ms11828 KiB
9Runtime error17ms11840 KiB
10Runtime error17ms12316 KiB
11Runtime error17ms12336 KiB
12Runtime error16ms12344 KiB
13Runtime error17ms12404 KiB
14Runtime error17ms12424 KiB
subtask40/15
15Runtime error16ms12532 KiB
16Runtime error17ms12748 KiB
17Runtime error17ms12508 KiB
18Runtime error17ms12544 KiB
19Runtime error17ms12756 KiB
20Runtime error17ms12948 KiB
21Runtime error17ms12808 KiB
subtask50/65
22Runtime error17ms12512 KiB
23Runtime error17ms12976 KiB
24Runtime error17ms12992 KiB
25Runtime error17ms13088 KiB
26Runtime error17ms13304 KiB
27Runtime error17ms13288 KiB
28Runtime error17ms13444 KiB
29Runtime error17ms13216 KiB
30Runtime error17ms13256 KiB
31Runtime error17ms13300 KiB
32Runtime error17ms13200 KiB
33Runtime error17ms13184 KiB
34Runtime error17ms13196 KiB
35Runtime error17ms12972 KiB
36Runtime error17ms13372 KiB
37Runtime error17ms13484 KiB
38Runtime error17ms13652 KiB
39Runtime error17ms13764 KiB
40Runtime error17ms13752 KiB