fork download
copy 
  1. //team : includenull
  2.  
  3. #include <cstdio>
  4. using namespace std;
  5. struct node
  6. {
  7. 	int value;
  8. 	int ans;
  9. 	int left,right,parent;
  10.  
  11. 	node(){
  12. 		value = 0;
  13. 		ans = 0;
  14. 		left = 0;
  15. 		right = 0;
  16. 		parent = 0;
  17. 	}
  18. };
  19.  
  20.  
  21.  
  22. void make_tree(node arr[],int num){
  23.  
  24. 	if (arr[num].left == 0 && arr[num].right == 0){
  25. 		if (arr[num].value == 0)
  26. 			arr[num].ans = 1;
  27. 	}
  28. 	if (arr[num].left != 0){
  29. 		make_tree(arr,arr[num].left);
  30. 		arr[num].ans += arr[arr[num].left].ans;
  31. 	}
  32. 	if (arr[num].right != 0){
  33. 		make_tree(arr,arr[num].right);
  34. 		arr[num].ans += arr[arr[num].right].ans;
  35. 	}
  36. }
  37.  
  38. void update_parent(node arr[],int num,int inc){
  39. 	if (num == 0)
  40. 		return;
  41.  
  42. 	arr[num].ans += inc;
  43. 	update_parent(arr,arr[num].parent,inc);
  44.  
  45. }
  46.  
  47. void update(node arr[],int num, int value){
  48. 	int prev= arr[num].value;
  49. 	arr[num].value += value;
  50.  
  51.  
  52. 	if (arr[num].value == 0 && prev !=0){
  53. 		arr[num].ans++;
  54. 		update_parent(arr,arr[num].parent,1);
  55. 	}
  56.  
  57. 	if (prev == 0 && arr[num].value != 0)
  58. 	{
  59. 		arr[num].ans--;
  60. 		update_parent(arr,arr[num].parent,-1);
  61. 	}
  62.  
  63.  
  64. }
  65.  
  66.  
  67.  
  68. int main(){
  69. 	int num,query,edge;
  70. 	int a,b;
  71. 	int i;
  72. 	char choice;
  73.  
  74. 	scanf ("%d %d",&num,&query);
  75. 	edge = num -1;
  76.  
  77. 	node arr[num + 2];
  78.  
  79.  
  80. 	for (i=0;i<edge ; i++){
  81. 		scanf ("%d %d",&a,&b);
  82. 		if (arr[a].left == 0){
  83. 			arr[a].left = b;
  84. 			arr[b].parent = a;
  85. 		}else{
  86. 			arr[a].right = b;
  87. 			arr[b].parent = a;
  88. 		}
  89. 	}
  90.  
  91. 	for (i=1; i<=num ; i++){
  92. 		scanf ("%d",&a);
  93. 		arr[i].value = a;
  94. 		// printf ("%d %d  ",i,arr[i].value);
  95. 	}
  96.  
  97. 	make_tree(arr,1);
  98.  
  99. 	// for (i=1;i<=num;i++)
  100. 	// {
  101. 	// 	printf("num = %d, parent= %d, left= %d,right= %d,value= %d,ans= %d\n",i,arr[i].parent,arr[i].left,arr[i].right,arr[i].value,arr[i].ans );
  102. 	// }
  103.  
  104. 	for (i=0 ; i<query; i++){
  105.  
  106. 		getchar_unlocked();
  107. 		scanf ("%c %d",&choice,&a);
  108. 		// printf ("%c %d\n",choice,a);
  109. 		if (choice == 'Q')
  110. 		{
  111. 			//scanf ("%d",&a);
  112. 			printf("%d\n",arr[a].ans );
  113. 		}else if (choice == 'U'){
  114. 			scanf ("%d",&b);
  115. 			update (arr,a,b);
  116. 		}else{
  117. 			printf ("%d in else\n",choice);
  118. 		}
  119.  
  120. 		// for (i=1;i<=num;i++)
  121. 		// {
  122. 		// 	printf("num = %d, parent= %d, left= %d,right= %d,value= %d,ans= %d\n",i,arr[i].parent,arr[i].left,arr[i].right,arr[i].value,arr[i].ans );
  123. 		// }
  124. 	}
  125.  
  126. 	// for (i=1;i<=num;i++)
  127. 	// {
  128. 	// 	printf("num = %d, parent= %d, left= %d,right= %d,value= %d,ans= %d\n",i,arr[i].parent,arr[i].left,arr[i].right,arr[i].value,arr[i].ans );
  129. 	// }
  130.  
  131.  
  132. 	return 0;
  133. }
Success #stdin #stdout 0s 3348KB
comments (?)
stdin
copy 
10 2
1 2
1 3
1 4
2 5
2 6
2 7
6 8
6 9
6 10
1 2 3 4 5 6 7 8 9 0
Q 6
Q 5
stdout
copy 
0
0
https://ideone.com/pY3KxU
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

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!