P17807 [ICPC 2019 Nanchang R] Bitwise Tree

给定一棵有 $n$ 个节点的树，节点编号为 $1$ 到 $n$，根节点为 $1$。树中每个节点都将被赋予与给定参数 $a_1, a_2, \cdots, a_n$ 相关的值，树中的每条边则被赋予一个给定的位运算符，运算符为按位或 `|`、按位与 `&`、按位异或 `^` 之一。 对于树中任意一对节点 $(u,v)$（分别表示第 $u$ 个和第 $v$ 个节点），连接它们的最短路径记作 $$ u=p_0, p_1, p_2, \cdots, p_{s-1}, p_s=v $$ 路径上的运算符按顺序给出一个与 $(u,v)$ 相关的值，计算方式为 $$ ((a_{p_0}\ opt_1\ a_{p_1})\ opt_2\ a_{p_2})\cdots opt_s\ a_{p_s}) $$ 其中 $opt_i$ 是该路径上节点 $p_{i-1}$ 与节点 $p_i$ 之间的边上的运算符。 现在给出 $q$ 个查询，每个查询包含两个整数 $d$ 和 $u$ $(1\le u\le n)$。对于该查询，第 $i$ 个节点的值将被设定为 $(a_i + i \times d)$，你需要计算所有满足第 $u$ 个节点是第 $v$ 个节点的祖先的节点对 $(u,v)$ 所对应的值的**按位或和**、**按位与和**以及**按位异或和**。注意，节点不被视为自身的祖先。

第一行包含两个整数 $n$ $(2 \le n \le 10^5)$ 和 $q$ $(1\le q\le 10^5)$，表示树的大小和查询的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$ $(1 \le a_i \le 10^{18})$，含义如上所述。 接下来的 $n-1$ 行描述树的结构。其中第 $i$ 行包含两个整数 $f$ $(1 \le f \le n)$ 和 $s$ $(0 \le s \le 2)$，表示第 $f$ 个节点是第 $(i+1)$ 个节点的父节点，且连接第 $(i+1)$ 个节点与第 $f$ 个节点的边被赋予了一个位运算符：若 $s=0$ 则运算符为 `|`；若 $s=1$ 则运算符为 `&`；若 $s=2$ 则运算符为 `^`。 接下来的 $q$ 行，每行包含两个整数 $d$ $(0\le d\le 100)$ 和 $u$ $(1\le u\le n)$，描述一个查询。数据保证节点 $u$ 不是树中的叶子。

输出 $q$ 行，对应 $q$ 个给定的查询，第 $i$ 行包含三个整数，分别表示第 $i$ 个查询的按位或和、按位与和以及按位异或和。

在样例中，树的形态如下： :::align{center}  ::: 对于第一个查询，按位或和为 $(1|2)~|~((1|2)|4)~|~((1|2)\&5)~|~(1\&3)~=~7$。 对于第二个查询，按位或和为 $(2|4)~|~(2\&5)~=~6$。 翻译由 DeepSeek V4 Pro 完成