Submission #1251426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251426		eirinayukari	Deblo (COCI18_deblo)	C++20	36 / 90	219 ms	16576 KiB

deblo

// XD XD
#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define el cout << "\n";

using namespace std;
using ll = long long;

const int MAXN = 1e5 + 7;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const ll LLINF = 1e18 + 7;

template <typename T>
bool ckmin(T& a, T b) {
    return a > b ? a = b, true : false;
}

template <typename T>
bool ckmax(T& a, T b) {
    return a < b ? a = b, true : false;
}

int n;
int a[MAXN];
vector<int> adj[MAXN];
int sz[MAXN], d[MAXN];
bool rev[MAXN];
ll ans;

void dfs(int u, int p) {
    sz[u] = 1;
    for (int v : adj[u]) {
        if (rev[v] || v == p) {
            continue;
        }

        dfs(v, u);
        sz[u] += sz[v];
    }
}

int centroid(int u, int p, int tot) {
    for (int v : adj[u]) {
        if (rev[v] || v == p) {
            continue;
        }

        if (sz[v] * 2 > tot) {
            return centroid(v, u, tot);
        }
    }

    return u;
}

vector<int> dfsXor(int u, int p) {
    d[u] = a[u] ^ d[p];
    vector<int> res = {d[u]};
    for (int v : adj[u]) {
        if (rev[v] || v == p) {
            continue;
        } 
        auto t = dfsXor(v, u);
        if (res.size() < t.size()) {
            swap(res, t);
        }

        for (auto &x : t) {
            res.push_back(x);
        }
    }
    return res;
}

void CD(int u) {
    dfs(u, 0);
    int ct = centroid(u, 0, sz[u]);
    rev[ct] = true;
    d[ct] = 0;
    vector<vector<int>> cnt(23, vector<int>(2, 0));

    for (auto v : adj[ct]) {
        if (rev[v]) {
            continue;
        }

        auto g = dfsXor(v, ct);
        for (auto &x : g) {
            ans += a[ct] ^ x;
            for (int i = 0; i <= 22; i++) {
                bool b = x >> i & 1;
                if (a[ct] >> i & 1) {
                    ans += 1LL * (1 << i) * cnt[i][b];
                } else {
                    ans += 1LL * (1 << i) * cnt[i][b ^ 1];
                }
            }
        }

        for (auto &x : g) {
            for (int i = 0; i <= 20; i++) {
                bool b = x >> i & 1;
                cnt[i][b]++;
            }
        }
    }

    for (auto v : adj[ct]) {
        if (rev[v]) {
            continue;
        }
        CD(v);
    }
}

void solve(int id) {
    // cout << "Case " << id << ": ";
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        ans += a[i];
    }

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    CD(1);
    cout << ans << "\n";
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++) {
        solve(i);
    }
    return 0;
}

• Subtask 1: 36 / 90