#P17807. [ICPC 2019 Nanchang R] Bitwise Tree
[ICPC 2019 Nanchang R] Bitwise Tree
题目描述
给定一棵有 个节点的树,节点编号为 到 ,根节点为 。树中每个节点都将被赋予与给定参数 相关的值,树中的每条边则被赋予一个给定的位运算符,运算符为按位或 |、按位与 &、按位异或 ^ 之一。
对于树中任意一对节点 (分别表示第 个和第 个节点),连接它们的最短路径记作
路径上的运算符按顺序给出一个与 相关的值,计算方式为
$$((a_{p_0}\ opt_1\ a_{p_1})\ opt_2\ a_{p_2})\cdots opt_s\ a_{p_s})$$其中 是该路径上节点 与节点 之间的边上的运算符。
现在给出 个查询,每个查询包含两个整数 和 。对于该查询,第 个节点的值将被设定为 ,你需要计算所有满足第 个节点是第 个节点的祖先的节点对 所对应的值的按位或和、按位与和以及按位异或和。注意,节点不被视为自身的祖先。
输入格式
第一行包含两个整数 和 ,表示树的大小和查询的数量。
第二行包含 个整数 ,含义如上所述。
接下来的 行描述树的结构。其中第 行包含两个整数 和 ,表示第 个节点是第 个节点的父节点,且连接第 个节点与第 个节点的边被赋予了一个位运算符:若 则运算符为 |;若 则运算符为 &;若 则运算符为 ^。
接下来的 行,每行包含两个整数 和 ,描述一个查询。数据保证节点 不是树中的叶子。
输出格式
输出 行,对应 个给定的查询,第 行包含三个整数,分别表示第 个查询的按位或和、按位与和以及按位异或和。
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}
:::
对于第一个查询,按位或和为 。
对于第二个查询,按位或和为 。
翻译由 DeepSeek V4 Pro 完成