#P2137. Gty的妹子树
Gty的妹子树
题目背景
我曾在弦歌之中听过你,
檀板声碎,半出折子戏。
舞榭歌台被风吹去,
岁月深处尚有余音一缕……
Gty 神(xian)犇(chong)从来不缺妹子……
他来到了一棵妹子树下,发现每个妹子有一个美丽度……
由于Gty很哲♂学,他只对美丽度大于某个值的妹子感兴趣。
他想知道某个子树中美丽度大于 的妹子个数。
某个妹子的美丽度可能发生变化……
树上可能会出现一只新的妹子……
题目描述
维护一棵初始有 个节点的有根树(根节点为 ),树上节点编号为 ,每个点有一个权值 。
支持以下操作:
-
0 u x
询问以 为根的子树中,严格大于 的值的个数。 -
1 u x
把 节点的权值改成 。 -
2 u x
添加一个编号为“当前树中节点数+1”的节点,其父节点为 ,其权值为 。
本题强制在线。
所有输入的 都需要异或 才是真正的输入。
其中 为上一次询问的答案,定义初始 。
输入格式
第一行一个正整数 ,表示初始节点数。
接下来 行,每行两个整数 ,为树上的一条无向边。
接下来一行 个整数 ,表示初始时每个节点的权值。
接着一行一个正整数 ,表示操作个数。
接下来 行,每行三个整数 ,表示一次操作。
输出格式
对每个 的操作,输出一行,包括一个整数,意义见题目描述。
2
1 2
10 20
1
0 1 5
2
2
1 2
10 20
1
0 1 10
1
提示
【数据范围】
对于 的数据,,,。