Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "bits/stdc++.h"
- using namespace std;
- typedef long long ll;
- typedef vector<ll> vi;
- typedef pair<ll, ll> pii;
- #define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
- #define repf(i, a, n) for (ll i = (a); i < (ll)(n); ++i)
- #define rrep(i, n) for (ll i = (n)-1; i >= 0; --i)
- #define rrepf(i, a, n) for (ll i = (n)-1; i >= a; --i)
- #define all(v) (v).begin(), (v).end()
- #ifdef ON99
- #include "debug.h"
- #else
- #define debug(...) 69
- #endif
- struct node
- {
- map<ll, ll> freq;
- map<ll, ll> sz_xor;
- map<ll, ll> sz_cnt;
- };
- void merge(node &a, node &b)
- {
- if (a.freq.size() < b.freq.size())
- swap(a, b);
- for (auto &[f, cnt] : b.freq)
- {
- a.sz_xor[a.freq[f]] ^= f;
- a.sz_cnt[a.freq[f]] -= 1;
- a.freq[f] += b.freq[f];
- a.sz_xor[a.freq[f]] ^= f;
- a.sz_cnt[a.freq[f]] += 1;
- }
- }
- node dfs(vi &ans, vector<vi> &G, vi &c, ll u, ll p)
- {
- node cur_node;
- cur_node.freq[c[u]] = 1;
- cur_node.sz_xor[1] = c[u];
- cur_node.sz_cnt[1] = 1;
- for (ll v : G[u])
- {
- if (v == p)
- continue;
- node new_node = dfs(ans, G, c, v, u);
- merge(cur_node, new_node);
- }
- auto it = cur_node.sz_cnt.lower_bound(1);
- while (it->second == 0)
- cur_node.sz_cnt.erase(it), it = cur_node.sz_cnt.lower_bound(it->first + 1);
- ans[u] = cur_node.sz_xor[it->first];
- return cur_node;
- }
- void solve(int _tc)
- {
- int n;
- cin >> n;
- vi v(n);
- rep(i, n) cin >> v[i];
- vector<vi> G(n);
- rep(i, n - 1)
- {
- int u, v;
- cin >> u >> v;
- --u, --v;
- G[u].push_back(v);
- G[v].push_back(u);
- }
- vi ans(n);
- dfs(ans, G, v, 0, 0);
- rep(i, n) cout << ans[i] << ' ';
- }
- // think twice, code once
- int main()
- {
- // freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- int tc = 1;
- // cin >> tc;
- rep(i, tc)
- solve(i);
- }
Advertisement
Add Comment
Please, Sign In to add comment