fork download
copy 
  1. //Jay Shree Krishna
  2.  
  3. #include <bits/stdc++.h>
  4. #include<ext/pb_ds/assoc_container.hpp>
  5. #include<ext/pb_ds/tree_policy.hpp>
  6.  
  7. using namespace std;
  8. using namespace __gnu_pbds;
  9.  
  10. #define ll long long
  11. #define pb push_back
  12. #define popb pop_back
  13. #define ff first
  14. #define ss second
  15. #define set_bits(x) __builtin_popcountll(x)
  16. #define sz(x) ((int)(x).size())
  17. #define all(x) (x).begin(), (x).end()
  18. #define mod 1000000007
  19. #define mod1 998244353
  20. typedef tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update > ordered_set;
  21. //find_by_order(k)  returns iterator to kth element starting from 0
  22. //order_of_key(k) returns count of elements strictly smaller than k
  23. //Ideas: BS, Prefix Suffix, Difference Array, Bits, Sorting, Try All Combinations
  24.  
  25. void dfs(int node, vector<vector<int>> &adj, vector<int> &res, vector<int> &vis, vector<int> &arr){
  26.     vis[node] = 1;
  27.     int f = 0;
  28.     map<int, int> mp;
  29.     for(auto ele : adj[node]){
  30.         if(vis[ele] == 0){
  31.             dfs(ele, adj, res, vis, arr);
  32.         }
  33.         if(arr[ele] == arr[node]){
  34.             res[arr[node]] = 1;
  35.         }
  36.         mp[arr[ele]]++;
  37.         if(mp[arr[ele]] > 1){
  38.             res[arr[ele]] = 1;
  39.         }
  40.     }
  41. }
  42.  
  43. int main(){
  44.     ios_base::sync_with_stdio(false);
  45.     cin.tie(NULL);
  46.     cout.tie(NULL);
  47.     int t;
  48.     cin >> t;
  49.     while(t--){
  50.         int n;
  51.         cin >> n;
  52.         vector<int> arr(n);
  53.         for(int i = 0 ; i < n ; i++){
  54.             cin >> arr[i];
  55.         }
  56.         vector<vector<int>> adj(n);
  57.         for(int i = 0 ; i + 1 < n ; i++){
  58.             int u, v;
  59.             cin >> u >> v;
  60.             u--;
  61.             v--;
  62.             adj[u].pb(v);
  63.             adj[v].pb(u);
  64.         }
  65.         vector<int> res(n + 1, 0);
  66.         vector<int> vis(n, 0);
  67.         dfs(0, adj, res, vis, arr);
  68.         for(int i = 1 ; i <= n ; i++){
  69.             cout << res[i];
  70.         }
  71.         cout << '\n';
  72.     }
  73. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
1
4
1 2 3 1
1 2
2 3
3 4
stdout
copy 
0000
https://ideone.com/j0uwn1
language:
C++14 (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!