Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
- // #pragma GCC optimize("O3")
- // #include <atcoder/fenwicktree>
- using namespace std;
- #define int long long
- using ll = long long;
- #define all(x) x.begin(), x.end()
- #define rall(x) x.rbegin(), x.rend()
- #define rep(i, n) for (int i = 0; i < n; ++i)
- #define rep1(i, n) for (int i = 1; i <= n; ++i)
- #define repp(i, s, n) for (int i = s; i < n; ++i)
- #define re(i, n) for (i = 0; i < n; ++i)
- int rd() {
- int i;
- cin >> i;
- return i;
- }
- template <typename T>
- void read(T &a) {
- cin >> a;
- }
- template <typename T, typename... Args>
- void read(T &a, Args &...args) {
- cin >> a;
- read(args...);
- }
- template <typename T>
- void print(T &&a) {
- cout << a;
- }
- template <typename T, typename... Args>
- void print(T &&a, Args &&...args) {
- cout << a;
- print(forward<Args>(args)...);
- }
- const int N = 1e5 + 10, K = 40;
- int c[N], ch[N*K][2], cnt = 0, root[N], ans[N];
- array<int, 2> t[N*K]; // [how many times, sum of dominatin]
- vector<int> g[N];
- array<int, 2> combine(array<int, 2> a, array<int, 2> b) {
- if (!a[0]) return b;
- if (!b[0]) return a;
- if (a[0] == b[0]) return {a[0], a[1] ^ b[1]};
- if (a[0] < b[0]) return a;
- return b;
- }
- void build(int &v, int x, int tl, int tr) {
- v = ++cnt;
- t[v] = {1, x};
- if (tl == tr) return;
- int tm = (tl + tr) / 2;
- if (x <= tm) build(ch[v][0], x, tl, tm);
- else build(ch[v][1], x, tm + 1, tr);
- }
- int merge(int t1, int t2) {
- // cout << "uwu" << t1 << " " << t2 << endl;
- if (!t1 || !t2) return t1 ^ t2; // return the non-zero value
- ch[t1][0] = merge(ch[t1][0], ch[t2][0]);
- ch[t1][1] = merge(ch[t1][1], ch[t2][1]);
- if (!ch[t1][0] && !ch[t1][1]) t[t1] = {t[t1][0]+t[t2][0], t[t1][1]};
- else t[t1] = combine(t[ch[t1][0]], t[ch[t1][1]]);
- // cout << t[t1][0] << " " << t[t1][1] << endl;
- return t1;
- }
- void dfs(int u, int p = -1) {
- for (int v : g[u]) {
- if (v == p) continue;
- dfs(v, u);
- // cout << "merging " << u << " " << v << endl;
- merge(root[u], root[v]);
- // cout << endl;
- }
- ans[u] = t[root[u]][1];
- }
- void solve() {
- int n = rd();
- for (int i = 1; i <= n; ++i) {
- c[i] = rd();
- build(root[i], c[i], 1, n);
- }
- for (int i = 1; i < n; ++i) {
- int x = rd(), y = rd();
- g[x].push_back(y);
- g[y].push_back(x);
- }
- dfs(1);
- for (int i = 1; i <= n; ++i) {
- cout << ans[i] << " \n"[i == n];
- }
- }
- signed main() {
- // #ifndef DEBUG
- // freopen("ugly.in", "r", stdin);
- // freopen("ugly.out", "w", stdout);
- // #endif
- // auto start = chrono::steady_clock::now();
- cin.tie(0)->sync_with_stdio(false);
- int tc = 1;
- cout << fixed << setprecision(10);
- // cin >> tc;
- //
- for (int i = 1; i <= tc; ++i) {
- // cerr << i << endl;
- // cout << "Case #" << i << ": ";
- // cerr << "case " << i << ":\n";
- solve();
- // cerr << endl;
- }
- // cerr << "final: "
- // << chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() -
- // start).count()
- // << "ms";
- }
Advertisement
Add Comment
Please, Sign In to add comment