Gty的妹子树

题目背景

我曾在弦歌之中听过你, 檀板声碎,半出折子戏。 舞榭歌台被风吹去, 岁月深处尚有余音一缕…… Gty神(xian)犇(chong)从来不缺妹子…… 他来到了一棵妹子树下,发现每个妹子有一个美丽度…… 由于Gty很哲♂学,他只对美丽度大于某个值的妹子感兴趣。 他想知道某个子树中美丽度大于k的妹子个数。 某个妹子的美丽度可能发生变化…… 树上可能会出现一只新的妹子……

题目描述

维护一棵初始有n个节点的有根树(根节点为1),树上节点编号为1-n,每个点有一个权值wi。 支持以下操作: 0 u x 询问以u为根的子树中,严格大于x的值的个数。(u^=lastans,x^=lastans) 1 u x 把u节点的权值改成x。(u^=lastans,x^=lastans) 2 u x 添加一个编号为"当前树中节点数+1"的节点,其父节点为u,其权值为x。(u^=lastans,x^=lastans) 最开始时lastans=0。

输入输出格式

输入格式


输入第一行包括一个正整数n(1<=n<=30000),代表树上的初始节点数。 接下来n-1行,每行2个整数u,v,为树上的一条无向边。 任何时刻,树上的任何权值大于等于0,且两两不同。 接下来1行,包括n个整数wi,表示初始时每个节点的权值。 接下来1行,包括1个整数m(1<=m<=30000),表示操作总数。 接下来m行,每行包括三个整数 op,u,x: op,u,x的含义见题目描述。 保证题目涉及的所有数在int内。

输出格式


对每个op=0,输出一行,包括一个整数,意义见题目描述。

输入输出样例

输入样例 #1

2
1 2
10 20
1
0 1 5

输出样例 #1

2

输入样例 #2

2
1 2
10 20
1
0 1 10

输出样例 #2

1

说明

时间限制每个测试点1s 空间限制128M