Guest User

Untitled

a guest
Oct 26th, 2022
176
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.78 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef vector<ll> vi;
  6. typedef pair<ll, ll> pii;
  7. #define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
  8. #define repf(i, a, n) for (ll i = (a); i < (ll)(n); ++i)
  9. #define rrep(i, n) for (ll i = (n)-1; i >= 0; --i)
  10. #define rrepf(i, a, n) for (ll i = (n)-1; i >= a; --i)
  11. #define all(v) (v).begin(), (v).end()
  12.  
  13. #ifdef ON99
  14. #include "debug.h"
  15. #else
  16. #define debug(...) 69
  17. #endif
  18.  
  19. struct node
  20. {
  21.     map<ll, ll> freq;
  22.     map<ll, ll> sz_xor;
  23.     map<ll, ll> sz_cnt;
  24. };
  25.  
  26. void merge(node &a, node &b)
  27. {
  28.     if (a.freq.size() < b.freq.size())
  29.         swap(a, b);
  30.     for (auto &[f, cnt] : b.freq)
  31.     {
  32.         a.sz_xor[a.freq[f]] ^= f;
  33.         a.sz_cnt[a.freq[f]] -= 1;
  34.         a.freq[f] += b.freq[f];
  35.         a.sz_xor[a.freq[f]] ^= f;
  36.         a.sz_cnt[a.freq[f]] += 1;
  37.     }
  38. }
  39.  
  40. node dfs(vi &ans, vector<vi> &G, vi &c, ll u, ll p)
  41. {
  42.     node cur_node;
  43.     cur_node.freq[c[u]] = 1;
  44.     cur_node.sz_xor[1] = c[u];
  45.     cur_node.sz_cnt[1] = 1;
  46.     for (ll v : G[u])
  47.     {
  48.         if (v == p)
  49.             continue;
  50.         node new_node = dfs(ans, G, c, v, u);
  51.         merge(cur_node, new_node);
  52.     }
  53.     auto it = cur_node.sz_cnt.lower_bound(1);
  54.     while (it->second == 0)
  55.         cur_node.sz_cnt.erase(it), it = cur_node.sz_cnt.lower_bound(it->first + 1);
  56.     ans[u] = cur_node.sz_xor[it->first];
  57.     return cur_node;
  58. }
  59.  
  60. void solve(int _tc)
  61. {
  62.     int n;
  63.     cin >> n;
  64.     vi v(n);
  65.     rep(i, n) cin >> v[i];
  66.     vector<vi> G(n);
  67.     rep(i, n - 1)
  68.     {
  69.         int u, v;
  70.         cin >> u >> v;
  71.         --u, --v;
  72.         G[u].push_back(v);
  73.         G[v].push_back(u);
  74.     }
  75.     vi ans(n);
  76.     dfs(ans, G, v, 0, 0);
  77.     rep(i, n) cout << ans[i] << ' ';
  78. }
  79.  
  80. // think twice, code once
  81. int main()
  82. {
  83.     // freopen("input.txt", "r", stdin);
  84.     // freopen("output.txt", "w", stdout);
  85.     ios_base::sync_with_stdio(0);
  86.     cin.tie(0);
  87.     int tc = 1;
  88.     // cin >> tc;
  89.     rep(i, tc)
  90.         solve(i);
  91. }
  92.  
Advertisement
Add Comment
Please, Sign In to add comment