Guest User

Untitled

a guest
Oct 26th, 2022
219
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.21 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  3. // #pragma GCC optimize("O3")
  4. // #include <atcoder/fenwicktree>
  5. using namespace std;
  6.  
  7. #define int long long
  8. using ll = long long;
  9. #define all(x) x.begin(), x.end()
  10. #define rall(x) x.rbegin(), x.rend()
  11. #define rep(i, n) for (int i = 0; i < n; ++i)
  12. #define rep1(i, n) for (int i = 1; i <= n; ++i)
  13. #define repp(i, s, n) for (int i = s; i < n; ++i)
  14.  
  15. #define re(i, n) for (i = 0; i < n; ++i)
  16. int rd() {
  17.     int i;
  18.     cin >> i;
  19.     return i;
  20. }
  21.  
  22. template <typename T>
  23. void read(T &a) {
  24.     cin >> a;
  25. }
  26.  
  27. template <typename T, typename... Args>
  28. void read(T &a, Args &...args) {
  29.     cin >> a;
  30.     read(args...);
  31. }
  32.  
  33. template <typename T>
  34. void print(T &&a) {
  35.     cout << a;
  36. }
  37.  
  38. template <typename T, typename... Args>
  39. void print(T &&a, Args &&...args) {
  40.     cout << a;
  41.     print(forward<Args>(args)...);
  42. }
  43.  
  44. const int N = 1e5 + 10, K = 40;
  45. int c[N], ch[N*K][2], cnt = 0, root[N], ans[N];
  46. array<int, 2> t[N*K]; // [how many times, sum of dominatin]
  47. vector<int> g[N];
  48. array<int, 2> combine(array<int, 2> a, array<int, 2> b) {
  49.     if (!a[0]) return b;
  50.     if (!b[0]) return a;
  51.     if (a[0] == b[0]) return {a[0], a[1] ^ b[1]};
  52.     if (a[0] < b[0]) return a;
  53.     return b;
  54. }
  55. void build(int &v, int x, int tl, int tr) {
  56.     v = ++cnt;
  57.     t[v] = {1, x};
  58.     if (tl == tr) return;
  59.     int tm = (tl + tr) / 2;
  60.     if (x <= tm) build(ch[v][0], x, tl, tm);
  61.     else build(ch[v][1], x, tm + 1, tr);
  62. }
  63. int merge(int t1, int t2) {
  64.     // cout << "uwu" << t1 << " " << t2 << endl;
  65.     if (!t1 || !t2) return t1 ^ t2; // return the non-zero value
  66.     ch[t1][0] = merge(ch[t1][0], ch[t2][0]);
  67.     ch[t1][1] = merge(ch[t1][1], ch[t2][1]);
  68.     if (!ch[t1][0] && !ch[t1][1]) t[t1] = {t[t1][0]+t[t2][0], t[t1][1]};
  69.     else t[t1] = combine(t[ch[t1][0]], t[ch[t1][1]]);
  70.     // cout << t[t1][0] << " " << t[t1][1] << endl;
  71.     return t1;
  72. }
  73. void dfs(int u, int p = -1) {
  74.     for (int v : g[u]) {
  75.         if (v == p) continue;
  76.         dfs(v, u);
  77.         // cout << "merging " << u << " " << v << endl;
  78.         merge(root[u], root[v]);
  79.         // cout << endl;
  80.     }
  81.     ans[u] = t[root[u]][1];
  82. }
  83. void solve() {
  84.     int n = rd();
  85.     for (int i = 1; i <= n; ++i) {
  86.         c[i] = rd();
  87.         build(root[i], c[i], 1, n);
  88.     }
  89.     for (int i = 1; i < n; ++i) {
  90.         int x = rd(), y = rd();
  91.         g[x].push_back(y);
  92.         g[y].push_back(x);
  93.     }
  94.     dfs(1);
  95.     for (int i = 1; i <= n; ++i) {
  96.         cout << ans[i] << " \n"[i == n];
  97.     }
  98. }
  99.  
  100. signed main() {
  101.     // #ifndef DEBUG
  102.     //     freopen("ugly.in", "r", stdin);
  103.     //     freopen("ugly.out", "w", stdout);
  104.     // #endif
  105.  
  106.     // auto start = chrono::steady_clock::now();
  107.  
  108.     cin.tie(0)->sync_with_stdio(false);
  109.  
  110.     int tc = 1;
  111.     cout << fixed << setprecision(10);
  112.     // cin >> tc;
  113.     //
  114.     for (int i = 1; i <= tc; ++i) {
  115.         // cerr << i << endl;
  116.         // cout << "Case #" << i << ": ";
  117.         // cerr << "case " << i << ":\n";
  118.         solve();
  119.         // cerr << endl;
  120.     }
  121.  
  122.     // cerr << "final: "
  123.     //      << chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() -
  124.     //      start).count()
  125.     //      << "ms";
  126. }
Advertisement
Add Comment
Please, Sign In to add comment