前两个点只有询问的过了，后面的 MLE

为什么会 MLE 啊，对拍也出不来

是常规的归并树+根号重构

数据生成器：（对拍时去掉了强制在线）

from random import*

l = 30000
r = 30000
V = 2**31 - 1

n = randint(l,r)
print(n)

fa = [i + 1 for i in range(n)]
shuffle(fa)
for i in range(2,n + 1):
	print(fa[i - 1],fa[randint(1,i - 1) - 1])
for i in range(n): print(randint(0,V),'',end='')
print()

m = randint(l,r)
print(m)

for i in range(m):
	op = randint(1,5)
	if op == 1: op = 0
	elif op <= 3: op = 1
	else: op = 2
	u = randint(1,n)
	x = randint(0,V)
	print(op,u,x)

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

const int N = 60001;
const int LOGN = 21;

inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); }
	do x = x * 10 + ch - 48, ch = getchar(); while(ch >= '0' && ch <= '9');
	return x * f;
}

int n,m,w[N],f[N][LOGN],dep[N];
int sz[N],son[N],num[N],rev[N],tot;
struct Edge {
	int u; Edge *nxt;
} *adj[N];
void Ins(int v,int u) {
	Edge *e = new Edge;
	e -> u = u, e -> nxt = adj[v];
	adj[v] = e;
}

void IDfs(int v,int fa) {
	f[v][0] = fa, dep[v] = dep[fa] + 1;
	for(int i = 1;i < LOGN;i++) f[v][i] = f[f[v][i - 1]][i - 1];
	for(Edge *i = adj[v];i;i = i -> nxt) {
		int u = i -> u;
		if(u == fa) continue;
		IDfs(u,v);
	}
	return;
}

void Dfs1(int v) {
	sz[v] = 1;
	for(Edge *i = adj[v];i;i = i -> nxt) {
		int u = i -> u;
		if(u == f[v][0]) continue;
		Dfs1(u), sz[v] += sz[u];
		if(sz[u] > sz[son[v]]) son[v] = u;
	}
	return;
}

void Dfs2(int v) {
	num[v] = ++tot, rev[tot] = v;
	if(son[v]) Dfs2(son[v]);
	for(Edge *i = adj[v];i;i = i -> nxt) {
		int u = i -> u;
		if(u == f[v][0] || u == son[v]) continue;
		Dfs2(u);
	}
	return;
}

int s[LOGN][N];

void Build(int d,int l,int r) {
	if(l == r) return void(s[d][l] = w[rev[l]]);
	int m = (l + r) >> 1;
	Build(d + 1,l,m), Build(d + 1,m + 1,r);
	int i = l, j = m + 1, c = l;
	while(i <= m && j <= r) {
		if(s[d + 1][i] < s[d + 1][j]) s[d][c++] = s[d + 1][i++];
		else s[d][c++] = s[d + 1][j++];
	}
	while(i <= m) s[d][c++] = s[d + 1][i++];
	while(j <= r) s[d][c++] = s[d + 1][j++];
	return;
}

int Query(int d,int l,int r,int x,int y,int v) {
	if(l >= x && r <= y)
		return r - (std::upper_bound(s[d] + l,s[d] + r + 1,v) - s[d] - 1);
	int m = (l + r) >> 1;
	if(y <= m) return Query(d + 1,l,m,x,y,v);
	else if(x > m) return Query(d + 1,m + 1,r,x,y,v);
	else return Query(d + 1,l,m,x,y,v) + Query(d + 1,m + 1,r,x,y,v);
}

bool Wrapped(int x,int y) {
	for(int i = LOGN - 1;i >= 0;i--) {
		if(dep[f[x][i]] >= dep[y]) x = f[x][i];
	}
	return x == y;
}

int nn;
int cg[N],lw[N],nw[N],tc;
int ad[N],ta;

void ReBuild() {
	tot = tc = ta = 0, n = nn;
	for(int i = 1;i <= n;i++) son[i] = 0;
	Dfs1(1), Dfs2(1);
	memset(s,0,sizeof(s));
	Build(1,1,n);
	return;
}

int main() {
	nn = n = read();
	for(int i = 2,v,u;i <= n;i++) {
		v = read(), u = read();
		Ins(v,u), Ins(u,v);
	}
	for(int i = 1;i <= n;i++) w[i] = read();
	IDfs(1,1), Dfs1(1), Dfs2(1);
	Build(1,1,n);
	m = read();
	int op,u,x,Sqrt = sqrt(m);
	int last = 0;
	while(m--) {
		op = read(), u = read() ^ last, x = read() ^ last;
		if(!op) {
			if(tc + ta > Sqrt) ReBuild();
			int ans = Query(1,1,n,num[u],num[u] + sz[u] - 1,x);
			for(int i = 1;i <= tc;i++) if(Wrapped(cg[i],u)) {
				if(lw[i] <= x && nw[i] > x) ans++;
				if(lw[i] > x && nw[i] <= x) ans--;
			}
			for(int i = 1;i <= ta;i++) if(Wrapped(ad[i],u) && w[ad[i]] > x) ans++;
			std::printf("%d\n",last = ans);
		} else if(op == 1) {
			cg[++tc] = u;
			lw[tc] = w[u];
			nw[tc] = w[u] = x;
		} else {
			Ins(++nn,u), Ins(u,nn);
			ad[++ta] = nn, w[nn] = x;
			f[nn][0] = u, dep[nn] = dep[u] + 1;
			for(int i = 1;i < LOGN;i++) f[nn][i] = f[f[nn][i - 1]][i - 1];
		}
	}
	return 0;
}