学到了询问分块的科技……
对于修改操作，每发生了\(S\)次修改就重构整棵树，小于\(S\)次的修改操作丢到一个队列里面。
对于每一次查询操作，先在主席树上查询当前子树内部大于\(k\)的节点的数量，然后依次将队列中的修改放到树上，在答案统计完成之后再将这些修改撤销。使用倍增检验某一个点是否在子树内，如果在子树内则考虑这个节点的权值修改或加入对于答案的影响。
修改的复杂度为\(O(\frac{N}{S}NlogN)\)，查询的复杂度为\(O(NSlogN)\)，当\(S = \sqrt{N}\)时有最优复杂度\(O(N \sqrt N logN)\)
因为分块的玄学性，\(S\)取\(\sqrt N\)可能会T，取\(\sqrt N logN\)跑得挺快。。。
#include<bits/stdc++.h>
#define mid ((l + r) >> 1)
#define st first
#define nd second
#define PII pair < int , int >
#define PIII pair < int , pair < int , int > >
//This code is written by Itst
using namespace std;
inline int read(){
int a = 0;
char c = getchar();
while(!isdigit(c))
c = getchar();
while(isdigit(c)){
a = a * 10 + c - 48;
c = getchar();
}
return a;
}
const int MAXN = 6e4 + 7;
struct Edge{
int end , upEd;
}Ed[MAXN << 1];
struct node{
int l , r , sum;
}Tree[MAXN * 30];
int head[MAXN] , val[MAXN] , dfn[MAXN] , sz[MAXN] , dep[MAXN] , jump[MAXN][21];
int N , N1 , M , T , ts , cntN , cntEd , cntL , lsh[MAXN] , rt[MAXN];
deque < PIII > q;
queue < PII > rev;
bool vis[MAXN];
inline void addEd(int a , int b){
Ed[++cntEd].end = b;
Ed[cntEd].upEd = head[a];
head[a] = cntEd;
}
int insert(int x , int l , int r , int tar){
int t = ++cntN;
Tree[t] = Tree[x];
++Tree[t].sum;
if(l != r)
if(mid >= tar)
Tree[t].l = insert(Tree[t].l , l , mid , tar);
else
Tree[t].r = insert(Tree[t].r , mid + 1 , r , tar);
return t;
}
void dfs(int x , int p){
dep[x] = dep[p] + 1;
dfn[x] = ++ts;
sz[x] = 1;
rt[ts] = insert(rt[ts - 1] , 1 , cntL , val[x]);
jump[x][0] = p;
for(int i = 1 ; jump[x][i - 1] ; ++i)
jump[x][i] = jump[jump[x][i - 1]][i - 1];
for(int i = head[x] ; i ; i = Ed[i].upEd)
if(Ed[i].end != p){
dfs(Ed[i].end , x);
sz[x] += sz[Ed[i].end];
}
}
inline void build(){
for(int i = 1 ; i <= N ; ++i)
lsh[i] = val[i];
sort(lsh + 1 , lsh + N + 1);
cntL = unique(lsh + 1 , lsh + N + 1) - lsh - 1;
for(int i = 1 ; i <= N ; ++i)
val[i] = lower_bound(lsh + 1 , lsh + cntL + 1 , val[i]) - lsh;
dfs(1 , 0);
}
inline void rebuild(){
cntN = ts = 0;
for(int i = 1 ; i <= N ; ++i)
val[i] = lsh[val[i]];
while(!q.empty()){
PIII t = q.front();
q.pop_front();
if(t.st == 1)
val[t.nd.st] = t.nd.nd;
else
addEd(jump[t.nd.st][0] , t.nd.st);
}
N = N1;
build();
}
int query(int x , int l , int r , int tar){
if(l == r || !x)
return 0;
if(mid >= tar)
return query(Tree[x].l , l , mid , tar) + Tree[Tree[x].r].sum;
else
return query(Tree[x].r , mid + 1 , r , tar);
}
inline int to(int x , int d){
for(int i = 16 ; i >= 0 ; --i)
if(dep[x] - (1 << i) >= d)
x = jump[x][i];
return x;
}
int get(int x , int v){
int sum , l = q.size();
if(v >= lsh[cntL])
sum = 0;
else
if(v < lsh[1])
sum = sz[x];
else
sum = query(rt[dfn[x] + sz[x] - 1] , 1 , cntL , upper_bound(lsh + 1 , lsh + cntL + 1 , v) - lsh - 1) - query(rt[dfn[x] - 1] , 1 , cntL , upper_bound(lsh + 1 , lsh + cntL + 1 , v) - lsh - 1);
for(int i = 0 ; i < l ; ++i){
int t = q[i].nd.st;
if(dep[t] < dep[x] || to(t , dep[x]) != x)
continue;
if(q[i].st == 1){
if(!vis[t]){
vis[t] = 1;
rev.push(PII(t , val[t]));
if(t <= N)
val[t] = lsh[val[t]];
}
if(val[t] <= v && q[i].nd.nd > v)
++sum;
else
if(val[t] > v && q[i].nd.nd <= v)
--sum;
val[t] = q[i].nd.nd;
}
else
if(val[t] > v)
++sum;
}
while(!rev.empty()){
PII t = rev.front();
rev.pop();
vis[t.st] = 0;
val[t.st] = t.nd;
}
return sum;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
N1 = N = read();
T = sqrt(N * log2(N));
for(int i = 1 ; i < N ; ++i){
int a = read() , b = read();
addEd(a , b);
addEd(b , a);
}
for(int i = 1 ; i <= N ; ++i)
val[i] = read();
build();
M = read();
int a , b , c , lastans = 0;
for(int i = 1 ; i <= M ; ++i){
a = read();
b = read() ^ lastans;
c = read() ^ lastans;
if(!a){
if(q.size() >= T)
rebuild();
printf("%d\n" , lastans = get(b , c));
}
else{
if(a == 2){
val[++N1] = c;
dep[N1] = dep[b] + 1;
jump[N1][0] = b;
for(int j = 1 ; jump[N1][j - 1] ; ++j)
jump[N1][j] = jump[jump[N1][j - 1]][j - 1];
}
q.push_back(PIII(a , PII(a == 2 ? N1 : b , c)));
}
}
return 0;
}