logo AlgoBeat OnlineJudge
登录 注册

#201116. Gty的妹子树

内存限制:125 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

我曾在弦歌之中听过你,

檀板声碎,半出折子戏。

舞榭歌台被风吹去,

岁月深处尚有余音一缕……

Gty 神(xian)犇(chong)从来不缺妹子……

他来到了一棵妹子树下,发现每个妹子有一个美丽度……

由于Gty很哲♂学,他只对美丽度大于某个值的妹子感兴趣。

他想知道某个子树中美丽度大于 的妹子个数。

某个妹子的美丽度可能发生变化……

树上可能会出现一只新的妹子……


维护一棵初始有 个节点的有根树(根节点为 ),树上节点编号为 ,每个点有一个权值

支持以下操作:

  • 0 u x 询问以 为根的子树中,严格大于 的值的个数。

  • 1 u x 节点的权值改成

  • 2 u x 添加一个编号为“当前树中节点数+1”的节点,其父节点为 ,其权值为

本题强制在线。
所有输入的 都需要异或 才是真正的输入。
其中 为上一次询问的答案,定义初始

输入格式

第一行一个正整数 ,表示初始节点数。

接下来 行,每行两个整数 ,为树上的一条无向边。

接下来一行 个整数 ,表示初始时每个节点的权值。

接着一行一个正整数 ,表示操作个数。

接下来 行,每行三个整数 ,表示一次操作。

输出格式

对每个 的操作,输出一行,包括一个整数,意义见题目描述。

样例

样例输入 1

2
1 2
10 20
1
0 1 5

样例输出 1

2

样例输入 2

2
1 2
10 20
1
0 1 10

样例输出 2

1

数据范围与提示

【数据范围】
对于 的数据,