#P2166. Gty的超级妹子树【数据疑似有误】

Gty的超级妹子树【数据疑似有误】

题目背景

我曾在青山之中遇过你,
新竹做杖,鬓插紫茱萸。
跣足踏过无边丝雨,
又拾起燕川雪片片落如席……

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

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

由于Gty很 哲♂学 也很 机♂智,他只对美丽度大于某个值的妹子感兴趣。
他想知道某个子树中美丽度大于 xx 的妹子个数。

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

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

但是……树枝可能会断裂,于是,Gty 惊讶地发现,他的面前变成了一片妹子树组成的森林……

题目描述

维护一棵初始有 nn 个节点的有根树(根节点为 11),树上节点编号为 1n1 \sim n,每个点有一个权值 wiw_i,它可能会变成森林。

支持以下操作:

  • 0 u x 询问以 uu 为根的子树中,严格大于 xx 的值的个数。
  • 1 u xuu 节点的权值改成 xx
  • 2 u x 添加一个编号为“当前树中节点数+1”的节点,其父节点为 uu,其权值为 xx
  • 3 u 删除 uu 与其父亲的边,并使 uu 变为其所在连通块的根。

本题强制在线。

所有输入的 u,xu,x 都需要异或 last\text{last} 才是真正的输入。其中 last\text{last} 为上一次询问的答案,定义初始 last=0\text{last} = 0

输入格式

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

接下来 n1n-1 行,每行两个整数 u,vu,v,为树上的一条无向边。

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

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

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

输出格式

对每个 op=0\text{op}=0 的操作,输出一行,包括一个整数,意义见题目描述。

2
1 2
10 20
1
0 1 5

2

提示

数据范围及约定

对于 100%100\% 的数据,1n,m1051\le n,m \le 10^51un1\le u \le n0wi,x<2310 \le w_i,x < 2^{31}