P17807 [ICPC 2019 Nanchang R] Bitwise Tree

You are given a tree with $n$ nodes labelled from $1$ to $n$, the root of which is the node labelled $1$. Every node in the tree will be endowed with values related to given parameters $a_1, a_2, \cdots, a_n$, and each edge in the tree is endowed with a given bitwise operator which is one of the bitwise OR `|`, the bitwise AND `&` and the bitwise XOR `^`. For any pair of nodes $(u,v)$ indicating the $u$-th and the $v$-th node in the tree, the shortest path connecting them in the tree, denoted by $$ u=p_0, p_1, p_2, \cdots, p_{s-1}, p_s=v $$ together with operators along the path provide a value associated with $(u,v)$ given by $$ ((a_{p_0}\ opt_1\ a_{p_1})\ opt_2\ a_{p_2})\cdots opt_s\ a_{p_s}) $$ where $opt_i$ is the operator on the edge between the node $p_{i-1}$ and the node $p_i$ in this path. Now you are given $q$ queries, each of which contains two integers $d$ and $u~(1\le u\le n)$. For this query, the value of the $i$-th node will be set to be $(a_i+i\times d)$, and you are asked to calculate the bitwise OR, AND and XOR sum respectively of values for all the pairs $(u,v)$ where the $u$-th node is an ancestor of the $v$-th node. Note that a node is not considered as an ancestor of itself.

The first line contains two integers $n~(2 \le n \le 10^5)$ and $q~(1\le q\le 10^5)$ indicating the size of the tree and the number of queries. The second line contains $n$ integers $a_1, a_2, \cdots, a_n~(1 \le a_i \le 10^{18})$ described as above. The following $n-1$ lines describe the tree. The $i$-th line of them contains two integers $f~(1 \le f \le n)$ and $s~(0 \le s \le 2)$ which describe that the $f$-th node is the parent node of the $(i+1)$-th node, and the edge connecting the $(i+1)$-th node and the $f$-th node is endowed with a bitwise operator: if $s=0$ the operator is `|`; if $s=1$ the operator is `&`; and if $s=2$ the operator is `^`. Each of the following $q$ lines contains two integers $d~(0\le d\le 100)$ and $u~(1\le u\le n)$ describing a query. It is guaranteed that the node $u$ is not a leaf in the tree.

Output $q$ lines corresponding to $q$ given queries, the $i$-th of which contains three integers representing the bitwise OR sum, the bitwise AND sum and the bitwise XOR sum for the $i$-th query respectively.

In the sample case, the tree looks like :::align{center}  ::: For the first query, the bitwise OR sum is $(1|2)~|~((1|2)|4)~|~((1|2)\&5)~|~(1\&3)~=~7$. For the second query, the bitwise OR sum is $(2|4)~|~(2\&5)~=~6$.