bzoj#P2908. 又是nand

又是nand

题目描述

首先知道 $A \operatorname{nand} B=\operatorname{not} (A \operatorname{and} B)$ (运算操作限制了数位位数为 kk)比如 2nand3,k=32 \operatorname{nand} 3,k=3,则 $2 \operatorname{nand} 3=\operatorname{not} (2 \operatorname{and} 3)=\operatorname{not} 2=5$。

给出一棵树,树上每个点都有点权,定义树上从 aabb 的费用为 00 与路径上的点的权值顺次 nand\operatorname{nand} 的结果,例如:从 22 号点到 55 号点顺次经过 2352\to 3\to 5,权值分别为 5,7,2,k=35,7,2,k=3,那么最终结果为 $0 \operatorname{nand} 5 \operatorname{nand} 7 \operatorname{nand} 2=7 \operatorname{nand} 7 \operatorname{nand} 2=0 \operatorname{nand} 2=7$,现在这棵树需要支持以下操作。

  1. Replace a b:将点 aa1an1\le a\le n)的权值改为 bb
  2. Query a b:输出点 aa 到点 bb 的费用。

请众神给出一个程序支持这些操作。

输入格式

  • 第一行 n,m,kn,m,k,树的节点数量、总操作个数和运算位数。
  • 接下来一行 nn 个数字,依次表示节点 ii 的权值。
  • 接下来 n1n-1 行,每行两个数字 a,ba,b1a,bn1\le a,b\le n)表示 a,ba,b 间有一条树边。
  • 接下来 mm 行,每行一个操作,为以上 22 类操作之一。

输出格式

  • 对于操作 22 每个输出一行,如题目所述。
3 3 3
2 7 3 
1 2
2 3
Query 2 3
Replace 1 3
Query 1 1
4
7

数据规模与约定

对于 100%100\% 的数据,n,m105n,m\le 10^5k32k\le 32