fork download 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <vector>
  4. #define N 1000007
  5. using namespace std;
  6.  
  7. vector <int> tree[100007]	;
  8. int level[N]	;
  9.  
  10. void dfs(int v, int pv){
  11.  
  12. 	level[v] = level[pv] + 1	;
  13. 	for (int i = 0; i < tree[v].size(); i++){
  14. 		if (tree[v][i] != pv)
  15. 			dfs(tree[v][i], v)	;
  16. 	}
  17. }
  18.  
  19. int main(){
  20.  
  21. 	int n, u, v	;
  22. 	scanf("%d", &n)	;
  23. 	if (n == 1){
  24.         printf("1\n")   ;
  25.         return 0    ;
  26.     }
  27. 	for (int i = 1; i < n; i++){
  28.  
  29. 		scanf("%d %d", &u, &v)	;
  30. 		tree[u].push_back(v)	;
  31. 		tree[v].push_back(u)	;
  32.  
  33. 	}
  34.  
  35. 	dfs(1, 0)	;
  36. 	int min1 = 0	;
  37. 	int min2 = 0	;
  38. 	for (int i = 1; i <=n ;i++){
  39.  
  40. 		if(level[i] % 2)
  41. 			min1++	;
  42. 		else
  43. 			min2++	;
  44. 	}
  45. 	printf("%d\n", min(min1, min2))	;
  46.  
  47. 	return 0	;
  48. }
  49.  
Success #stdin #stdout 0s 8552KB
comments ()
stdin 
1
1 3
1 2
stdout 
1
https://ideone.com/gKm7B3
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!