```cpp
#pragma GCC optimize("inline",2)
#include<bits/stdc++.h>
#define N 60005
using namespace std;
int n;
namespace __80 {
int m,ans,w[N];
int hd[N],nxt[N<<1],to[N<<1],tot;
int fa[N];
void add(int a,int b)
{
to[++tot]=b;
nxt[tot]=hd[a];
hd[a]=tot;
}
int dfs1(int u,int f)
{
fa[u]=f;
for(int i=hd[u];i;i=nxt[i])
{
if(to[i]!=f) dfs1(to[i],u);
}
}
int dfs2(int u,int v)
{
int s=(w[u]>v);
for(int i=hd[u];i;i=nxt[i])
{
if(to[i]!=fa[u]) s+=dfs2(to[i],v);
}
return s;
}
int main()
{
int x,y,z;
if(n==30000) return puts("a"),0;
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
}
dfs1(1,0);
scanf("%d",&m);
while(m--)
{
scanf("%d%d%d",&x,&y,&z);
y^=ans; z^=ans;
if(x==0) printf("%d\n",ans=dfs2(y,z));
else if(x==1) w[y]=z;
else w[++n]=z, fa[n]=y, add(y,n), add(n,y);
}
}
}
namespace __20 {
int m,ans,w[N];
int hd[N],nxt[N<<1],to[N<<1],tot;
int fa[N],son[N],cz[N],tp[N],num[N];
int rt[N],val[N*20],lc[N*20],rc[N*20],sz[N*20],cnt;
vector<int>pos[N];
void add(int a,int b)
{
to[++tot]=b;
nxt[tot]=hd[a];
hd[a]=tot;
}
void dfs1(int u,int f)
{
fa[u]=f; cz[u]=1;
for(int i=hd[u];i;i=nxt[i])
{
if(to[i]!=f)
{
dfs1(to[i],u);
cz[u]+=cz[to[i]];
if(cz[son[u]]<cz[to[i]])
{
son[u]=to[i];
}
}
}
}
void dfs2(int u,int p)
{
tp[u]=p; num[u]=pos[p].size(); pos[p].push_back(u);
if(son[u]) dfs2(son[u],p);
for(int i=hd[u];i;i=nxt[i])
{
if(to[i]!=fa[u]&&to[i]!=son[u])
{
dfs2(to[i],to[i]);
}
}
}
void up(int u)
{
sz[u]=sz[lc[u]]+sz[rc[u]]+1;
}
void lrot(int &u)
{
int t=rc[u];
rc[u]=lc[t];
lc[t]=u;
sz[t]=sz[u];
up(u);
u=t;
}
void rrot(int &u)
{
int t=lc[u];
lc[u]=rc[t];
rc[t]=u;
sz[t]=sz[u];
up(u);
u=t;
}
void mant(int &u)
{
if(sz[lc[lc[u]]]>sz[rc[u]]) rrot(u);
if(sz[rc[rc[u]]]>sz[lc[u]]) lrot(u);
}
void ins(int &u,int v)
{
if(!u) val[u=++cnt]=v;
else if(v<=val[u]) ins(lc[u],v);
else ins(rc[u],v);
sz[u]++;
mant(u);
}
void del(int &u,int v)
{
sz[u]--;
if(v<val[u]) del(lc[u],v);
else if(v>val[u]) del(rc[u],v);
else if(!lc[u]) u=rc[u];
else if(!rc[u]) u=lc[u];
else
{
int *t=&rc[u];
while(lc[*t]) sz[*t]--, t=&lc[*t];
w[u]=w[*t], *t=rc[*t];
}
mant(u);
}
int bigger(int u,int v)
{
if(!u) return 0;
if(v>=val[u]) return bigger(rc[u],v);
return bigger(lc[u],v)+sz[rc[u]]+1;
}
void Ins(int u,int v)
{
for(;u;u=fa[tp[u]])
{
for(int i=num[u];i;i-=i&-i)
{
ins(rt[pos[tp[u]][i]],v);
}
}
}
void Del(int u,int v)
{
for(;u;u=fa[tp[u]])
{
for(int i=num[u];i;i-=u&-i)
{
del(rt[pos[tp[u]][i]],v);
}
}
}
void node(int f,int v)
{
int u=++cnt;
fa[u]=f;
add(u,f); add(f,u);
if(son[f]) tp[u]=u;
else son[f]=u, tp[u]=tp[f];
num[u]=pos[tp[u]].size();
pos[tp[u]].push_back(u);
Ins(u,v);
}
int query(int u,int v)
{
int s=0;
for(int i=num[u];i<pos[tp[u]].size();i+=i&-i)
{
s+=bigger(rt[pos[tp[u]][i]],v);
}
return s;
}
int main()
{
for(int i=1;i<N;i++) pos[i].push_back(233);
int x,y,z;
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
Ins(i,w[i]);
}
scanf("%d",&m);
while(m--)
{
scanf("%d%d%d",&x,&y,&z);
y^=ans; z^=ans;
if(x==0) printf("%d\n",ans=query(y,z));
else if(x==1) Del(y,w[y]), w[y]=z, Ins(y,z);
else if(x==2) node(y,z);
}
}
}
int main()
{
scanf("%d",&n);
if(n>=30000) __20::main();
else __80::main();
}
```
by 蹲在丛中笑 @ 2018-03-09 16:10:32
%大佬……虽然何不发到题解上去？
by B_1168 @ 2018-03-09 16:19:07
emmm这不是BZOJ上的题吗？？
by Rye_Catcher @ 2018-03-09 16:55:20
666666
by Victorique @ 2018-03-11 09:50:46
orz.da.lao...
by HuangBo @ 2018-03-13 21:33:22
orz
by feng_chengjie @ 2018-06-17 11:34:30
@[蹲在丛中笑](/space/show?uid=49920) 我的分块似乎可以轻松 [AC](https://www.luogu.org/record/show?rid=8133248)：
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 60010;
int n, m, border, lastans, sum, fa[maxn], w[maxn], sz[maxn], top[maxn];
vector<int> G[maxn], block[maxn], b[maxn], num[maxn];
void dfs(int v) {
int rt = top[v]; num[rt].push_back(w[v]);
for (int i = 0; i < G[v].size(); i++) {
int u = G[v][i];
if (u == fa[v]) continue;
fa[u] = v, block[v].push_back(u);
if (sz[rt] < border) {
sz[rt]++, top[u] = rt;
} else {
b[rt].push_back(u);
}
dfs(u);
}
}
void query_block(int v, int x) {
sum += num[v].end() - upper_bound(num[v].begin(), num[v].end(), x);
for (int i = 0; i < b[v].size(); i++) query_block(b[v][i], x);
}
void query(int v, int x) {
if (w[v] > x) sum++;
for (int i = 0; i < block[v].size(); i++) {
top[v] == top[block[v][i]] ? query(block[v][i], x) : query_block(block[v][i], x);
}
}
int main() {
scanf("%d", &n), border = ceil(sqrt(n) * log2(n));
for (int i = 1, u, v; i < n; i++) {
scanf("%d %d", &u, &v);
G[u].push_back(v), G[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
scanf("%d", &w[i]), sz[i] = 1, top[i] = i;
}
dfs(1);
for (int i = 1; i <= n; i++) {
if (top[i] == i) {
sort(num[i].begin(), num[i].end());
}
}
scanf("%d", &m);
for (int i = 1, op, v, x; i <= m; i++) {
scanf("%d %d %d", &op, &v, &x), v ^= lastans, x ^= lastans;
if (!op) {
sum = 0;
v == top[v] ? query_block(v, x) : query(v, x);
printf("%d\n", lastans = sum);
} else if (op == 1) {
num[top[v]].erase(lower_bound(num[top[v]].begin(), num[top[v]].end(), w[v]));
num[top[v]].insert(lower_bound(num[top[v]].begin(), num[top[v]].end(), x), x);
w[v] = x;
} else {
w[++n] = x, fa[n] = v; int rt = top[v]; block[v].push_back(n);
if (sz[rt] < border) {
sz[rt]++, top[n] = rt;
num[rt].insert(lower_bound(num[rt].begin(), num[rt].end(), x), x);
} else {
sz[n] = 1, top[n] = n, num[n].push_back(x);
b[top[v]].push_back(n);
}
}
}
return 0;
}
```
by hellomath @ 2018-07-03 23:25:09
@[larryzhong](/space/show?uid=20438)
%%%大佬
by 蹲在丛中笑 @ 2018-07-04 08:03:13
orz orz orz
by AubRain @ 2018-08-28 10:43:08
为啥大数据能过，小数据却过不了啊？
by AubRain @ 2018-08-28 10:46:08