CF600E divide and conquer

// Problem: E. Lomsat gelral
// Contest: Codeforces - Educational Codeforces Round 2
// URL: https://codeforces.com/problemset/problem/600/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#ifndef __DEBUG__
#define dbg(...) 42
#endif
template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vi = vector<int>;
using a2l = array<ll, 2>;

int main(int argc, char **argv)
{
    int n, x, y;
    cin >> n;
    vi vc(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> vc[i];
    vector<vi> g(n + 1);
    for (int i = 1; i < n; ++i)
        cin >> x >> y, g[x].push_back(y), g[y].push_back(x);

    int dcnt = 0;
    vi dfn(n + 1), idx(n + 1), dsize(n + 1);
    function<int(int, int)> dfs = [&](int u, int fa) {
        dsize[u] = 1, dfn[u] = ++dcnt, idx[dcnt] = u;
        for (auto v : g[u])
            if (v != fa)
                dsize[u] += dfs(v, u);
        return dsize[u];
    };
    dfs(1, -1);

    vl ans(n + 1);
    vi ccnt(n + 1), opts;
    ll max_freq = 0, acc = 0;
    auto inc_color_cnt = [&](int c) -> ll {
        opts.push_back(c);
        ccnt[c] += 1;
        if (ccnt[c] == max_freq) {
            acc += c;
        } else if (ccnt[c] > max_freq) {
            max_freq = ccnt[c];
            acc = c;
        }
        return acc;
    };
    auto clear_color = [&]() {
        max_freq = acc = 0;
        while (opts.size()) {
            ccnt[opts.back()]--;
            opts.pop_back();
        }
    };
    function<void(int, int)> bisearch = [&](int l, int r) {
        if (l == r) {
            ans[idx[l]] = vc[idx[l]];
            return;
        }

        int mid = l + r >> 1;
        bisearch(l, mid), bisearch(mid + 1, r);
        clear_color();

        int p = mid;
        for (int i = mid; i >= l; --i) {
            int j = i + dsize[idx[i]] - 1;
            if (j > r)
                break;
            ll last = inc_color_cnt(vc[idx[i]]);
            if (j <= mid)
                continue;
            while (p < j)
                last = inc_color_cnt(vc[idx[++p]]);
            ans[idx[i]] = last;
        }
    };
    bisearch(1, n);

    for (int i = 1; i <= n; ++i)
        cout << ans[i] << ' ';
    cout << endl;
};