[CCPC2020长春F] Strange Memory

[CCPC2020长春F] Strange Memory - 树上启发式合并

Description

给出一棵 n 个点组成的有根树，一号节点是根节点，现在要求 (sumlimits_{i=1}^nsumlimits_{j=i+1}^n [a_i oplus a_j = a_{operatorname{lca}(i, j)}] (i oplus j).)

Solution

可能因为数据比较随机，所以直接做一个简单的树上启发式合并就能卡过去，正解还得按位拆分一下

对于每个点，维护它的子树中，每个 (x) 对应的所有满足 (a[i]=x) 的 (i)，用 map 套 vector 维护

跑一遍 DFS，到一个点考虑它作为 LCA 的贡献，边跑边做合并

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e5 + 5;

map<int, vector<int>> f[N];
vector<int> g[N];

int n, a[N], ans;

void dfs(int p, int from = 0)
{
    for (int q : g[p])
    {
        if (q == from)
            continue;
        dfs(q, p);
        if (f[p].size() < f[q].size())
            swap(f[p], f[q]);
        for (auto &[val, vec] : f[q])
        {
            int key = val ^ a[p];
            if (f[p].count(key))
            {
                auto &v = f[p][key];
                // 循环顺序会影响效率？！
                for (auto i : vec)
                    for (auto j : v)
                    {
                        ans += i ^ j;
                    }
            }
        }
        for (auto &[val, vec] : f[q])
        {
            for (auto i : vec)
            {
                f[p][val].push_back(i);
            }
        }
    }
    f[p][a[p]].push_back(p);
}

signed main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i < n; i++)
    {
        int p, q;
        cin >> p >> q;
        g[p].push_back(q);
        g[q].push_back(p);
    }
    dfs(1);
    cout << ans << endl;
}