听说 CSP 前帮助别人会涨 rp

WA on test#7

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define int long long

using namespace std;

using LL = long long;
using ULL = unsigned long long;
const int N = 100010, M = N << 2;
const int K = 8e7;
const ULL INF = (1ll << 31) + 1ll;
int n, m, lastans, fa[N], top[N];
int idx, ch[K][2], sz[K], st[N];
int h[N], e[M], ne[M], tot, w[N];
vector<int> node;

void add(int a, int b) {
	e[ ++ tot] = b, ne[tot] = h[a], h[a] = tot;
}
struct Trie {
	int root;
	#define F for (int i = 32, x = root, t; ~i; i -- )
	void ins(int v, int c) {
		F {
			if (!ch[x][t = v >> i & 1ll]) ch[x][t] = ++ idx;
			sz[x = ch[x][t]] += c;
		}
	}
	int rk(int v, int res = 0) {
		F {
			if ((t = v >> i & 1ll)) res += sz[ch[x][0]];
			x = ch[x][t];
		} return res;
	}
}tr[N];

void dfs1(int u, int Fa, int t) {
	fa[u] = Fa; top[u] = t;
	for (int i = h[u]; i; i = ne[i]) {
		int v = e[i]; if (v == Fa) continue;
		if (!st[v]) dfs1(v, u, t); 
		else dfs1(v, u, v);
	}
}
void dfs2(int u, int rt) {
	tr[rt].ins(w[u], 1);
	for (int i = h[u]; i; i = ne[i]) {
		int v = e[i]; if (v == fa[u]) continue;
		dfs2(v, rt);
	}
}
void build() {
	for (int i = 1; i <= idx; i ++ )
		ch[i][0] = ch[i][1] = sz[i] = 0;
	idx = 0;
	node.clear();
	int S = (int)sqrt(n);
	st[1] = 1; node.push_back(1);
	for (int i = 2; i <= S; i ++ ) {
		int x = rand() % n + 1;
		st[x] = i; node.push_back(x);
	} 
	for (auto i : node) tr[i].root = ++ idx;
	dfs1(1, 0, 1);
	for (auto i : node)
		dfs2(i, i);
}
int query(int u, int x) {
	if (st[u]) {
		return tr[u].rk(INF) - tr[u].rk(x + 1);
	} int ans = (w[u] > x);
	for (int i = h[u]; i; i = ne[i]) {
		int v = e[i]; if (v == fa[u]) continue;
		ans += query(v, x);
	} return ans;
}
void modify(int u, int x) {
	int now = u;
	while (top[now]) {
		tr[top[now]].ins(w[u], -1);
		tr[top[now]].ins(x, 1);
		now = fa[top[now]];
	} w[u] = x;
}
void insert(int u, int x) {
	n ++ ; add(u, n); add(n, u); w[n] = x;
	fa[n] = u; top[n] = top[u];
	int now = n;
	while (top[now]) tr[top[now]].ins(x, 1), now = fa[top[now]];
}
signed main() {
	scanf("%lld", &n);
	for (int i = 1; i < n; i ++ ) {
		int a, b; scanf("%lld%lld", &a, &b);
		add(a, b), add(b, a);
	}
	for (int i = 1; i <= n; i ++ )
		scanf("%lld", &w[i]);
	build();
	scanf("%lld", &m);
	while (m -- ) {
		int op, u, x;
		scanf("%lld%lld%lld", &op, &u, &x);
		u ^= lastans, x ^= lastans;
		if (op == 0) printf("%lld\n", lastans = query(u, x));
		if (op == 1) modify(u, x);
		if (op == 2) insert(u, x);
	} return 0;
}