fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5. inline int power(int a, int b) {
  6.     int x = 1;
  7.     while (b) {
  8.         if (b & 1) x *= a;
  9.         a *= a;
  10.         b >>= 1;
  11.     }
  12.     return x;
  13. }
  14.  
  15.  
  16. const int M = 1000000007;
  17. const int N = 3e5+9;
  18. const int INF = 2e9+1;
  19. const int LINF = 2000000000000000001;
  20.  
  21. //_ ***************************** START Below *******************************
  22.  
  23.  
  24.  
  25. vector<vector<int>> edges;
  26. vector<int> coins;
  27.  
  28. //? Approach 1 : Eager deleting leaf nodes 
  29.  
  30. //* We instantly delete leaf nodes 
  31.  
  32. //? Algo : Topo Sort == Leaf Pruning + Smart BFS 
  33. //* Topo Sort : 
  34. //* 	Gurantees traversal from Leaf Nodes => Inside of graph / Tree
  35.  
  36. //* 	Here we are performing Multi Source BFS from Leaf nodes 
  37. //* 	Hence we are processing child -> parent (reverse direction)
  38.  
  39. void consistency1(int n) {
  40.  
  41. 	vector<vector<int>> graph(n);
  42. 	for(int i=0; i<n-1; i++){
  43. 		int x = edges[i][0], y = edges[i][1];
  44. 		graph[x].push_back(y);
  45. 		graph[y].push_back(x);
  46. 	}
  47.  
  48. 	int removed = 0;
  49. 	vector<int> degree(n);
  50. 	queue<int> q;
  51.  
  52.  
  53. 	//* Step 0 : Multi Source BFS to recursively delete all leave nodes  with 0's
  54. 	for(int i=0; i<n; i++){
  55. 		degree[i] = graph[i].size();
  56. 		if(degree[i] == 1 && coins[i] == 0){
  57. 			q.push(i);
  58. 		}
  59. 	}
  60.  
  61. 	while(!q.empty()){
  62. 		removed++;
  63. 		auto ch = q.front(); q.pop();
  64.  
  65. 		int parent = -1;
  66.  
  67. 		//* We are processing reverse i.e. child -> parent edge 
  68. 		//* (not parent -> child  edge )
  69. 		for(auto& par : graph[ch]){
  70. 			degree[par]--;
  71. 			parent = par;
  72. 			if(degree[par] == 1 && coins[par] == 0){
  73. 				q.push(par);
  74. 			}
  75. 		}
  76.  
  77. 		//* Since we are processing child -> parent  edge 
  78. 		//* 	We need find parent of child and delete from both side
  79. 		if(parent != -1){
  80. 			auto ch_to_delete = find(graph[parent].begin(), graph[parent].end(), ch);
  81. 			graph[parent].erase(ch_to_delete);
  82.  
  83. 			auto par_to_delete = find(graph[ch].begin(), graph[ch].end(), parent);
  84. 			graph[ch].erase(par_to_delete );
  85. 		}
  86. 	}
  87.  
  88.  
  89. 	//* Step1 : Multi source BFS to delete all leaf nodes with 1's 
  90. 	//* After deleting all 0's leaf nodes, we are guranteed to have leaf nodes with all 1's
  91. 	for(int i=0; i<n; i++){
  92. 		degree[i] = graph[i].size();
  93. 		if(degree[i] == 1 ){
  94. 			q.push(i);
  95. 		}
  96. 	}
  97.  
  98. 	while(!q.empty()){
  99. 		removed++;
  100. 		auto ch = q.front(); q.pop();
  101.  
  102. 		int parent = -1;
  103.  
  104. 		for(auto& par : graph[ch]){
  105. 			degree[par]--;
  106. 			parent = par;
  107. 		}
  108.  
  109.  
  110. 		if(parent != -1){
  111. 			auto ch_to_delete = find(graph[parent].begin(), graph[parent].end(), ch);
  112. 			graph[parent].erase(ch_to_delete);
  113.  
  114. 			auto par_to_delete = find(graph[ch].begin(), graph[ch].end(), parent);
  115. 			graph[ch].erase(par_to_delete );
  116. 		}
  117. 	}
  118.  
  119.  
  120. 	//* Step 2 : Multi source BFS to delete all leaf nodes with 1's or 0's (dont matter) 
  121. 	//* This leaf might contain 0 or 1
  122. 	for(int i=0; i<n; i++){
  123. 		degree[i] = graph[i].size();
  124. 		if(degree[i] == 1 ){
  125. 			q.push(i);
  126. 		}
  127. 	}
  128.  
  129. 	while(!q.empty()){
  130. 		removed++;
  131. 		auto ch = q.front(); q.pop();
  132.  
  133. 		int parent = -1;
  134.  
  135. 		for(auto& par : graph[ch]){
  136. 			degree[par]--;
  137. 			parent = par;
  138. 		}
  139.  
  140. 		if(parent != -1){
  141. 			auto ch_to_delete = find(graph[parent].begin(), graph[parent].end(), ch);
  142. 			graph[parent].erase(ch_to_delete);
  143.  
  144. 			auto par_to_delete = find(graph[ch].begin(), graph[ch].end(), parent);
  145. 			graph[ch].erase(par_to_delete );
  146. 		}
  147. 	}
  148.  
  149. 	int left = n - removed;
  150.  
  151. 	if(left <= 0) cout << 0 << " ";
  152. 	else cout << 2 * (left - 1) << " ";
  153.  
  154. }
  155.  
  156.  
  157.  
  158.  
  159.  
  160.  
  161.  
  162.  
  163.  
  164.  
  165. //? Approach 2 : lazy deleting leaf nodes 
  166.  
  167. // void consistency2(int n) {
  168.  
  169. // 	vector<vector<int>> graph(n);
  170. // 	for(int i=0; i<n-1; i++){
  171. // 		int x = edges[i][0], y = edges[i][1];
  172. // 		graph[x].push_back(y);
  173. // 		graph[y].push_back(x);
  174. // 	}
  175.  
  176. // 	int removed = 0;
  177. // 	vector<int> degree(n);
  178. // 	queue<int> q;
  179. // 	vector<bool> deleted(n);
  180.  
  181. // 	//* Step 0 : Multi Source BFS to recursively delete all leave nodes 
  182. // 	for(int i=0; i<n; i++){
  183. // 		degree[i] = graph[i].size();
  184. // 		if(degree[i] == 1 && coins[i] == 0){
  185. // 			q.push(i);
  186. // 		}
  187. // 	}
  188.  
  189. // 	while(!q.empty()){
  190. // 		auto ch = q.front(); q.pop();
  191.  
  192. // 		deleted[ch] = true;
  193. // 		removed++;
  194.  
  195.  
  196. // 		for(auto& par : graph[ch]){
  197. // 			if(deleted[par]) continue;
  198. // 			degree[par]--;
  199. // 			if(degree[par] == 1 && coins[par] == 0){
  200. // 				q.push(par);
  201. // 			}
  202. // 		}
  203.  
  204.  
  205. // 	}
  206.  
  207.  
  208. // 	//* Step1 : Multi source BFS to delete all leaf nodes with 1's 
  209. // 	//* After deleting all 0's leaf nodes, we are guranteed to have leaf nodes with all 1's
  210. // 	for(int i=0; i<n; i++){
  211. // 		degree[i] = graph[i].size();
  212. // 		if(degree[i] == 1 && !deleted[i] ){
  213. // 			q.push(i);
  214. // 		}
  215. // 	}
  216.  
  217. // 	while(!q.empty()){
  218. // 		auto ch = q.front(); q.pop();
  219.  
  220. // 		deleted[ch] = true;
  221. // 		removed++;
  222.  
  223. // 		for(auto& par : graph[ch]){
  224. // 			if(deleted[par]) continue;
  225. // 			degree[par]--;
  226. // 			if(degree[par] == 1){
  227. // 				q.push(par);
  228. // 			}
  229. // 		}
  230.  
  231. // 	}
  232.  
  233.  
  234. // 	//* Step 2 : Multi source BFS to delete all leaf nodes with 1's or 0's (dont matter) 
  235. // 	//* This leaf might contain 0 or 1
  236. // 	for(int i=0; i<n; i++){
  237. // 		degree[i] = graph[i].size();
  238. // 		if(degree[i] == 1 ){
  239. // 			q.push(i);
  240. // 		}
  241. // 	}
  242.  
  243. // 	while(!q.empty()){
  244. // 		auto ch = q.front(); q.pop();
  245.  
  246. // 		deleted[ch] = true;
  247. // 		removed++;
  248.  
  249. // 		for(auto& par : graph[ch]){
  250. // 			if(deleted[par]) continue;
  251. // 			degree[par]--;
  252. // 			if(deleted[par] == 1){
  253. // 				q.push(par);
  254. // 			}
  255. // 		}
  256. // 	}
  257.  
  258. // 	int left = n - removed;
  259.  
  260. // 	if(left <= 0) cout << 0 << " ";
  261. // 	else cout << 2 * (left - 1) << " ";
  262.  
  263. // }
  264.  
  265.  
  266.  
  267. void solve() {
  268.  
  269. 	int n;
  270. 	cin >> n;
  271.  
  272. 	coins.resize(n);
  273. 	edges.resize(n-1);
  274.  
  275. 	for(int i=0; i<n; i++) cin >> coins[i];
  276.  
  277. 	for(int i=0; i<n-1; i++){
  278. 		int x, y;
  279. 		cin >> x >> y;
  280. 		edges[i] = {x, y};
  281. 	}
  282.  
  283.     consistency1(n);
  284.     consistency2(n);
  285.  
  286. 	cout << endl;
  287. }
  288.  
  289.  
  290.  
  291.  
  292.  
  293. int32_t main() {
  294.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  295.  
  296.     int t = 1;
  297.     // cin >> t;
  298.     while (t--) {
  299.         solve();
  300.     }
  301.  
  302.     return 0;
  303. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
11
0 0 1 1 0 0 0 0 0 1 1 
0 1
0 2
0 6
1 3
1 4
3 10
4 5
6 7
7 8 
8 9
stdout
copy 
6 0
https://ideone.com/2jCpn1
language:
C++14 (gcc 8.3)
created:
7 hours 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!