出题人题解 | #异或树#

原题解链接：https://ac.nowcoder.com/discuss/153563

按位处理+线段树合并。

首先按位处理，那么问题转化为求一个子树内，权值大于 $x$ 的， $1$ （或 $0$ ）的个数。

可以对每棵子树建立一棵权值线段树，每个叶子节点维护两个值 $s i z e$ 和 $c n t []$ ，表示这个权值出现的次数，以及这个权值二进制分解后，每一位上 $1$ 的个数。权值线段树每个节点维护 $c n t []$ ，表示子树内二进制下每一位上 $1$ 的个数和，现在可以在 $O (l o g^{2} V)$ 处理每个关于子树 $u$ 的询问了， $V$ 是值域。

然后 $d f s$ 过程中，线段树合并来维护每个节点的权值线段树，线段树合并的过程中是合并到叶子节点的，合并的过程同时记录每个叶子节点出现的次数，出现偶数次就是代表这个权值消失了。


#include<cstdio>
#include<iostream>
#include<vector>
#include<stack>
#include<cstring>
#define pa pair<int,int>
#define mp make_pair
using namespace std;
typedef long long LL;
const int N = 100005, B = 19;
struct Edge{ int to, nxt; } e[N * 2];
struct Node{ 
	int Leaf, a[21]; 
	Node() {Leaf = 0; memset(a, 0, sizeof(a));}
} T[N * 20];
int cnt[N * 20], ls[N * 20], rs[N * 20], w[N], head[N], fa[N], siz[N], Enum, Index, n, m, Size, Vmax;
LL ans[N];
vector< pa > Q[N];
stack<int> ID;

Node operator + (const Node &x,const Node &y) {
    Node res;
    for (int i = 0; i <= B; ++i) res.a[i] = x.a[i] + y.a[i];
    return res;
}
void add_edge(int u,int v) {
    ++Enum; e[Enum].to = v; e[Enum].nxt = head[u]; head[u] = Enum; 
}
int NewNode() {
    int k;
    if (!ID.empty()) k = ID.top(), ID.pop();
    else k = ++Index;
    ls[k] = rs[k] = cnt[k] = 0;
    for (int i = 0; i <= B; ++i) T[k].a[i] = 0; T[k].Leaf = 0;
    return k;
}
void Insert(int l,int r,int &rt,int x) {
    if (!rt) rt = NewNode();
    if (l == r) { 
    	T[rt].Leaf = x;
        cnt[rt] ^= 1;
        if (cnt[rt]) for (int i = 0; i <= B; ++i) T[rt].a[i] = ((x >> i) & 1);
        else for (int i = 0; i <= B; ++i) T[rt].a[i] = 0;
        return ; 
    }
    int mid = (l + r) >> 1;
    if (x <= mid) Insert(l, mid, ls[rt], x);
    else Insert(mid + 1, r, rs[rt], x);
    T[rt] = T[ls[rt]] + T[rs[rt]];
    cnt[rt] = cnt[ls[rt]] + cnt[rs[rt]];
}
Node query(int l,int r,int rt,int L,int R) {
    if (L <= l && r <= R) { Size += cnt[rt]; return T[rt]; }
    int mid = (l + r) >> 1;
    if (R <= mid) return query(l, mid, ls[rt], L, R);
    else if (L > mid) return query(mid + 1, r, rs[rt], L, R);
    else return query(l, mid, ls[rt], L, R) + query(mid + 1, r, rs[rt], L, R);
}
int Merge(int x,int y) {
    if (!x || !y) return x + y;
    if (T[x].Leaf && T[y].Leaf) {
    	if (T[x].Leaf == T[y].Leaf) {
	    	cnt[x] = (cnt[y] + cnt[x]) % 2;
	        if (!cnt[x]) for (int i = 0; i <= B; ++i) T[x].a[i] = 0;
	        else for (int i = 0; i <= B; ++i) T[x].a[i] = ((T[x].Leaf >> i) & 1);
		} else {
			cnt[x] = cnt[x] + cnt[y]; T[x] = T[x] + T[y];
		}
		ID.push(y);
		return x;
	}
    ls[x] = Merge(ls[x], ls[y]);
    rs[x] = Merge(rs[x], rs[y]);
    T[x] = T[ls[x]] + T[rs[x]];
	cnt[x] = cnt[ls[x]] + cnt[rs[x]];
    ID.push(y);
    return x;
}
int dfs(int u) {
    int rt = NewNode();
    siz[u] = 1;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (v == fa[u]) continue;
        fa[v] = u;
        int t = dfs(v);
        rt = Merge(rt, t);
        siz[u] += siz[v];
    }
    Insert(1, Vmax, rt, w[u]);
    for (int i = 0; i < (int)Q[u].size(); ++i) {
        int x = Q[u][i].first, id = Q[u][i].second;
        Size = 0;
        Node now = query(1, Vmax, rt, x + 1, Vmax);
        for (int j = 0; j <= B; ++j) {
            if ((x >> j) & 1) ans[id] += 1ll * (1 << j) * (Size - now.a[j]);
            else ans[id] += 1ll * (1 << j) * now.a[j];
        }
    }
    return rt;
}
int main() { 
    int u, v, x;
    scanf("%d%d", &n, &m); Vmax = n + 1;
    for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);
    for (int i = 1; i <= n; ++i) {
        if (w[i] < 1 || w[i] > n) cout << "!!!!!!!!!";
    }
    
    for (int i = 1; i < n; ++i) {
        scanf("%d%d", &u, &v);
        add_edge(u, v), add_edge(v, u);
    }
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &u, &x);
        Q[u].push_back(mp(x, i));
    }
    dfs(1);
    for (int i = 1; i <= m; ++i) printf("%lld\n", ans[i]);
    return 0;
}