33OJ
登录 注册

#P17807. [ICPC 2019 Nanchang R] Bitwise Tree

    ID: 20406 远端评测题 8000ms 512MiB 尝试: 0 已通过: 0 显示难度省选/NOI− 上传者: 标签>动态规划 DP2019树形 DPICPC

[ICPC 2019 Nanchang R] Bitwise Tree

题目描述

给定一棵有 nn 个节点的树,节点编号为 11 到 nn,根节点为 11。树中每个节点都将被赋予与给定参数 a1,a2,⋯ ,ana_1, a_2, \cdots, a_n 相关的值,树中的每条边则被赋予一个给定的位运算符,运算符为按位或 |、按位与 &、按位异或 ^ 之一。

对于树中任意一对节点 (u,v)(u,v)(分别表示第 uu 个和第 vv 个节点),连接它们的最短路径记作

u=p0,p1,p2,⋯ ,ps−1,ps=vu=p_0, p_1, p_2, \cdots, p_{s-1}, p_s=v

路径上的运算符按顺序给出一个与 (u,v)(u,v) 相关的值,计算方式为

$$((a_{p_0}\ opt_1\ a_{p_1})\ opt_2\ a_{p_2})\cdots opt_s\ a_{p_s})$$

其中 optiopt_i 是该路径上节点 pi−1p_{i-1} 与节点 pip_i 之间的边上的运算符。

现在给出 qq 个查询,每个查询包含两个整数 dd 和 uu (1≤u≤n)(1\le u\le n)。对于该查询,第 ii 个节点的值将被设定为 (ai+i×d)(a_i + i \times d),你需要计算所有满足第 uu 个节点是第 vv 个节点的祖先的节点对 (u,v)(u,v) 所对应的值的按位或和、按位与和以及按位异或和。注意,节点不被视为自身的祖先。

输入格式

第一行包含两个整数 nn (2≤n≤105)(2 \le n \le 10^5) 和 qq (1≤q≤105)(1\le q\le 10^5),表示树的大小和查询的数量。

第二行包含 nn 个整数 a1,a2,⋯ ,ana_1, a_2, \cdots, a_n (1≤ai≤1018)(1 \le a_i \le 10^{18}),含义如上所述。

接下来的 n−1n-1 行描述树的结构。其中第 ii 行包含两个整数 ff (1≤f≤n)(1 \le f \le n) 和 ss (0≤s≤2)(0 \le s \le 2),表示第 ff 个节点是第 (i+1)(i+1) 个节点的父节点,且连接第 (i+1)(i+1) 个节点与第 ff 个节点的边被赋予了一个位运算符:若 s=0s=0 则运算符为 |;若 s=1s=1 则运算符为 &;若 s=2s=2 则运算符为 ^。

接下来的 qq 行,每行包含两个整数 dd (0≤d≤100)(0\le d\le 100) 和 uu (1≤u≤n)(1\le u\le n),描述一个查询。数据保证节点 uu 不是树中的叶子。

输出格式

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

5 4
1 2 3 4 5
1 0
1 1
2 0
2 1
0 1
0 2
1 2
2 2
7 1 4
6 0 6
12 0 12
14 6 8

提示

在样例中,树的形态如下:

:::align{center} :::

对于第一个查询,按位或和为 (1∣2) ∣ ((1∣2)∣4) ∣ ((1∣2)&5) ∣ (1&3) = 7(1|2)~|~((1|2)|4)~|~((1|2)\&5)~|~(1\&3)~=~7。

对于第二个查询,按位或和为 (2∣4) ∣ (2&5) = 6(2|4)~|~(2\&5)~=~6。

翻译由 DeepSeek V4 Pro 完成