题目内容

某个由 $n$ 台路由器组成的层级网络恰好包含 $n-1$ 条双向链路，并保证网络无环、连通。将所有路由器编号为 $1$ 到 $n$ 并指定 $1$ 号路由器为网络中心。从中心出发可以唯一确定上下级关系：对于任意路由器 $u$，与中心方向直接相连的路由器称为其上级，其余直接相连的路由器称为其下级；没有下级的路由器称为终端路由器，其余称为中继路由器。

每台路由器 $i$ 均有一个信号值 $a_i$。定义路由器的效能值如下：

• 若 $u$ 为终端路由器，则其效能值 $w_u = a_u$；
• 若 $u$ 为中继路由器，则其效能值为$$w_u = \max\{\,a_u \oplus a_v \mid v ext{ 为 } u ext{ 的下级}\,\}$$ 其中 $\oplus$ 表示按位异或运算。

现在需要依次处理 $m$ 项操作，操作类型有三种：