fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. vector<int> g[100001];  //To store graph(tree)
  4. int ans[100001];  //DP Table
  5.  
  6. int dyn(int root){
  7. 	//If answer is pretabulated return tabulated value
  8. 	if( ans[root]!=-1 ) return ans[root];	
  9.  
  10. 	//Answer of current sub-tree if we take its root into the vertex cover set :-
  11. 	int ans_inc=1;	// 1  for the root
  12. 	for(int x=0;x<g[root].size();x++) ans_inc+=dyn(g[root][x]);	//Adding answers of all its children
  13.  
  14. 	//Answer of current sub-tree if we don't take its root into the vertex cover set:-
  15. 	int ans_exc=g[root].size(); //g[root].size() for no.of children
  16. 	for(int x=0;x<g[root].size();x++){
  17. 		int child=g[root][x]; //for each child of root
  18. 		for(int y=0;y<g[child].size();y++) //add answers of all its children(i.e grandchildren of root)
  19. 			ans_exc+=dyn(g[child][y]);
  20. 	}
  21.  
  22. 	//return minimum of both cases
  23. 	return ans[root]=min(ans_inc,ans_exc);
  24. }
  25.  
  26. int main(void){
  27. 	int n; 
  28. 	scanf("%d",&n);
  29. 	for(int i=1;i<n+1;i++) ans[i]=-1;
  30. 	int root;
  31. 	for(int i=0;i<n-1;i++){
  32. 		int a; 
  33. 		scanf("%d",&a);
  34. 		int b; 
  35. 		scanf("%d",&b);
  36. 		if( i==0 or b==root ) root=a;
  37. 		g[a].push_back(b);
  38. 	}
  39. 	printf("%d",dyn(root));
  40. }
Success #stdin #stdout 0s 5032KB
comments (?)
stdin
copy 
3
1 2
1 3
stdout
copy 
1
https://ideone.com/mmA6jx
language:
C++14 (gcc 8.3)
created:
7 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!