fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5.  
  6. const int N = 500005;
  7.  
  8. vector<int> adj[N];   // Adjacency list for the tree
  9. int a[N];             // Values at nodes
  10. int subtree_size[N];  // Subtree sizes
  11. map<int, int> freq;   // Frequency map
  12. int n;
  13.  
  14. void dfs(int node, int parent, map<int, int>& count, string& result) {
  15.     count[a[node]]++;  // Increment frequency of value at this node
  16.     subtree_size[node] = 1;
  17.  
  18.     // Traverse children
  19.     for (int child : adj[node]) {
  20.         if (child == parent) continue;
  21.  
  22.         map<int, int> child_count;
  23.         dfs(child, node, child_count, result);
  24.  
  25.         // Merge smaller map into the larger one for efficiency
  26.         if (child_count.size() > count.size()) swap(child_count, count);
  27.  
  28.         for (auto [key, val] : child_count) count[key] += val;
  29.  
  30.         subtree_size[node] += subtree_size[child];
  31.     }
  32.  
  33.     // Check for majority condition
  34.     int majority_threshold = subtree_size[node] / 2;
  35.     bool is_majority = false;
  36.  
  37.     for (auto [value, count_val] : count) {
  38.         if (count_val > majority_threshold) {
  39.             is_majority = true;
  40.             break;
  41.         }
  42.     }
  43.  
  44.     result[node - 1] = (is_majority ? '1' : '0');  // Convert to 0-based index
  45. }
  46.  
  47. void solve() {
  48.     cin >> n;
  49.  
  50.     // Reset adjacency list for each test case
  51.     for (int i = 1; i <= n; i++) {
  52.         adj[i].clear();
  53.     }
  54.  
  55.     // Read values at each node
  56.     for (int i = 1; i <= n; i++) {
  57.         cin >> a[i];
  58.     }
  59.  
  60.     // Read edges
  61.     for (int i = 1; i < n; i++) {
  62.         int u, v;
  63.         cin >> u >> v;
  64.         adj[u].push_back(v);
  65.         adj[v].push_back(u);
  66.     }
  67.  
  68.     string result(n, '0');
  69.     map<int, int> count;
  70.     dfs(1, -1, count, result);
  71.  
  72.     cout << result << '\n';
  73. }
  74.  
  75. signed main() {
  76.     ios::sync_with_stdio(false);
  77.     cin.tie(0);
  78.  
  79.     int t;
  80.     cin >> t;
  81.     while (t--) {
  82.         solve();
  83.     }
  84.  
  85.     return 0;
  86. }
  87.  
Success #stdin #stdout 0.01s 18316KB
comments (?)
stdin
copy 
4
3
1 2 3
1 3
2 3
4
3 1 1 3
1 2
2 3
4 2
4
2 4 4 2
1 2
2 3
3 4
13
1 4 4 7 4 7 1 1 7 11 11 11 11
1 2
2 3
3 4
4 5
4 6
2 7
7 8
2 9
6 10
5 11
11 12
10 13
stdout
copy 
010
0111
0101
0001111111111
https://ideone.com/czrQBU
language:
C++ (gcc 8.3)
created:
12 days 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!