bzoj#P2908. 又是nand
又是nand
题目描述
首先知道 $A \operatorname{nand} B=\operatorname{not} (A \operatorname{and} B)$ (运算操作限制了数位位数为 )比如 ,则 $2 \operatorname{nand} 3=\operatorname{not} (2 \operatorname{and} 3)=\operatorname{not} 2=5$。
给出一棵树,树上每个点都有点权,定义树上从 到 的费用为 与路径上的点的权值顺次 的结果,例如:从 号点到 号点顺次经过 ,权值分别为 ,那么最终结果为 $0 \operatorname{nand} 5 \operatorname{nand} 7 \operatorname{nand} 2=7 \operatorname{nand} 7 \operatorname{nand} 2=0 \operatorname{nand} 2=7$,现在这棵树需要支持以下操作。
Replace a b
:将点 ()的权值改为 。Query a b
:输出点 到点 的费用。
请众神给出一个程序支持这些操作。
输入格式
- 第一行 ,树的节点数量、总操作个数和运算位数。
- 接下来一行 个数字,依次表示节点 的权值。
- 接下来 行,每行两个数字 ()表示 间有一条树边。
- 接下来 行,每行一个操作,为以上 类操作之一。
输出格式
- 对于操作 每个输出一行,如题目所述。
3 3 3
2 7 3
1 2
2 3
Query 2 3
Replace 1 3
Query 1 1
4
7
数据规模与约定
对于 的数据,,。