2020 China Collegiate Programming Contest Changchun Onsite F. Strange Memory

题目描述

https://codeforces.com/gym/102832/problem/F

简要题意：给定一棵有 $n$ 个节点的数，每个点有一个权值 $a_i$，求 $\sum_{i=1}^n\sum_{j=i+1}^na_i\oplus a_j=a_{lca(i,j)}$，其中 $\oplus$ 表示异或

$n\le 10^5,a_i\le 10^6$

Solution

我们考虑对于每一个点 $u$，计算其子树内的贡献，那么对于子树内枚举出的点 $v$，可以得到剩下那个点的另一个点权 $a[w]$ 一定为 $a[u]~xor~a[v]$

然后对于 $(v~xor~w)$ 这一个贡献，我们可以拆位来计算

对于每个点 $u$，枚举子树内所有 $lca$ 是 $u$ 的点对中的一个点的做法就是 $DSU$

时间复杂度 $O(n\log^2 n)$

#include <iostream>
#include <cstdio>
#include <set>
#include <stack>
#include <cstring>
#include <algorithm> 
#define maxn 100010
#define maxm 1200010
#define ll long long
using namespace std;

int n, m, a[maxn];

struct Edge {
    int to, next;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

int son[maxn], sz[maxn], in[maxn], out[maxn], bl[maxn], c2;
void Dfs(int u, int fa) {
    int Max = 0; sz[u] = 1; in[u] = ++c2; bl[c2] = u; 
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue;
        Dfs(v, u); sz[u] += sz[v];
        if (sz[v] > Max) Max = sz[v], son[u] = v;
    } out[u] = c2;
}

int cnt[maxm][20][2];
inline void add(int u) {
    for (int i = in[u]; i <= out[u]; ++i) {
        int v = bl[i];
        for (int o = 0; o < 20; ++o) ++cnt[a[v]][o][v >> o & 1]; 
    } 
}

inline void del(int u) {
    for (int i = in[u]; i <= out[u]; ++i) {
        int v = bl[i];
        for (int o = 0; o < 20; ++o) --cnt[a[v]][o][v >> o & 1]; 
    }
}

ll ans;
void dfs(int u, int fa) {
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa || v == son[u]) continue;
        dfs(v, u); del(v); 
    }
    if (son[u]) dfs(son[u], u);
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa || v == son[u]) continue;
        for (int j = in[v]; j <= out[v]; ++j) {
            int w = bl[j];
            for (int o = 0; o < 20; ++o) ans += (1ll << o) * cnt[a[w] ^ a[u]][o][(w >> o & 1) ^ 1];
        }
        add(v); 
    }
    for (int o = 0; o < 20; ++o) ++cnt[a[u]][o][u >> o & 1];
}

int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i < n; ++i) {
        int x, y; cin >> x >> y;
        add_edge(x, y); add_edge(y, x);
    } Dfs(1, 0); dfs(1, 0); cout << ans << "\n"; 
    return 0;
}