Description：

三种操作，查询某个子树严格大于 $x$ 的值的个数，修改点权，添加一个叶子。

$1\leqslant n\leqslant 30000$

Solution：

动态的树分块，也很好理解，如果父节点的块的大小大于等于 $\sqrt n$ 就单开一块，这样每个块一定联通，在每个块内排序，二分查找是 $O(\log n)$ 的，不难发现块也形成了一个树结构，每次从询问根节点开始 $dfs$ ，如果遇到了别的块，那么这个块一定完整在子树中，于是在块的那个树上再 $dfs$ 计算就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m;

#define MAXN 60010

int w[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

vector<int> g[MAXN];

int ins[MAXN];

int blo = 0,siz[MAXN];

vector<int> v[MAXN];

int f[MAXN];

void extend(int k,int fa,int val)

{

	f[k] = fa;

	w[k] = val;

	if(fa == 0 || siz[ins[fa]] >= sqrt(n))

	{

		++blo;

		siz[blo] = 1;

		v[blo].push_back(val);

		ins[k] = blo;

		g[ins[fa]].push_back(ins[k]);

		return;

	}

	else

	{

		++siz[ins[fa]];

		ins[k] = ins[fa];

		v[ins[fa]].push_back(val);

		sort(v[ins[fa]].begin(),v[ins[fa]].end());

		return;

	}

}

void dfs(int k,int fa)

{

	extend(k,fa,w[k]);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa)continue;

		dfs(e[i].to,k);

	}

	return;

}

int calc(int k,int val)

{

	int ans = v[k].size() - (upper_bound(v[k].begin(),v[k].end(),val) - v[k].begin());

	for(vector<int>::iterator it = g[k].begin();it != g[k].end();++it)ans += calc(*it,val);

	return ans;

}

int calc(int rt,int k,int v)

{

	if(ins[k] != ins[rt])return calc(ins[k],v);

	int ans = (w[k] > v);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == f[k])continue;

		ans += calc(rt,e[i].to,v);

	}

	return ans;

}

void change(int k,int val)

{

	for(int i = 0;i < v[ins[k]].size();++i)if(v[ins[k]][i] == w[k])v[ins[k]][i] = val;

	sort(v[ins[k]].begin(),v[ins[k]].end());

	w[k] = val;

	return;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i < n;++i)add(rd(),rd());

	for(int i = 1;i <= n;++i)w[i] = rd();

	dfs(1,0);

	int lastans = 0;

	scanf("%d",&m);

	int op,x,y;

	int tot = n;

	for(int i = 1;i <= m;++i)

	{

		op = rd();x = rd() ^ lastans;y = rd() ^ lastans;

		if(op == 0)printf("%d\n",lastans = calc(x,x,y));

		if(op == 1)change(x,y);

		if(op == 2)++tot,extend(tot,x,y),add(x,tot);

	}

	return 0;

}