题目描述

我曾在弦歌之中听过你， 檀板声碎，半出折子戏。 舞榭歌台被风吹去， 岁月深处尚有余音一缕…… 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,v： op,u,v的含义见题目描述。 保证题目涉及的所有数在int内。

输出格式

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

2
1 2
10 20
1
0 1 5

2

提示

没有写明提示

题目来源

By Autumn