fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5.  
  6.  
  7. const int M = 1000000007;
  8. const int N = 3e5+9;
  9. const int INF = 2e9+1;
  10. const int MAXN = 100000;
  11. const int LINF = 2000000000000000001;
  12.  
  13. //_ ***************************** START Below *******************************
  14.  
  15.  
  16.  
  17.  
  18. vector<vector<int>> tree;
  19. vector<int> nodes;
  20.  
  21. void consistency(int n){
  22.  
  23. 	vector<int> dp(n+1, 0); // 1 indexing
  24. 	if(nodes[1] == 1) dp[1] = 1;
  25.  
  26. 	queue<int> q;
  27. 	q.push(1);
  28.  
  29. 	vector<int> visited(n+1, false);
  30. 	visited[1] = true;
  31.  
  32.  
  33. 	while(!q.empty()){
  34. 		auto v = q.front(); q.pop();
  35. 		int count = 0;
  36. 		for(int u : tree[v]){
  37. 			if(visited[u]){
  38. 				//* Parent 
  39.  
  40. 				//* This wont be checked as Tree has only 1 path
  41. 			}
  42. 			else{
  43. 				//* child of Parent
  44. 				q.push(u);
  45. 				visited[u] = true;
  46. 				dp[u] += dp[v];
  47. 				if(nodes[u] == 1) dp[u]++;
  48. 			}
  49.  
  50. 		}
  51. 	}
  52.  
  53.  
  54.  
  55. 	for(int i=1; i<=n; i++){
  56. 		cout << dp[i] << " ";
  57. 	}cout << endl;
  58.  
  59. }
  60.  
  61.  
  62.  
  63. void solve() {
  64.  
  65. 	int n;
  66. 	cin >> n;
  67.  
  68. 	tree.resize(n+1); // 1 based indexing
  69. 	nodes.resize(n+1);
  70. 	for(int i=1; i<=n; i++) cin >> nodes[i];
  71.  
  72. 	for(int i=0; i<n-1; i++){
  73. 		int x, y;
  74. 		cin >> x >> y;
  75. 		tree[x].push_back(y);
  76. 		tree[y].push_back(x);
  77. 	}
  78.  
  79. 	consistency(n);
  80.  
  81. }
  82.  
  83.  
  84.  
  85.  
  86.  
  87. int32_t main() {
  88.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  89.  
  90.     int t = 1;
  91.     while (t--) {
  92.         solve();
  93.     }
  94.  
  95.     return 0;
  96. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
5 
0 1 1 0 0
1 2
1 3
2 4
3 5
stdout
copy 
0 1 1 1 1
https://ideone.com/SYZCWW
language:
C++14 (gcc 8.3)
created:
2 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!