#P17807. [ICPC 2019 Nanchang R] Bitwise Tree
[ICPC 2019 Nanchang R] Bitwise Tree
Problem Description
You are given a tree with nodes labelled from to , the root of which is the node labelled . Every node in the tree will be endowed with values related to given parameters , 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 indicating the -th and the -th node in the tree, the shortest path connecting them in the tree, denoted by
together with operators along the path provide a value associated with given by
$$((a_{p_0}\ opt_1\ a_{p_1})\ opt_2\ a_{p_2})\cdots opt_s\ a_{p_s})$$where is the operator on the edge between the node and the node in this path.
Now you are given queries, each of which contains two integers and . For this query, the value of the -th node will be set to be , and you are asked to calculate the bitwise OR, AND and XOR sum respectively of values for all the pairs where the -th node is an ancestor of the -th node. Note that a node is not considered as an ancestor of itself.
Input Format
The first line contains two integers and indicating the size of the tree and the number of queries.
The second line contains integers described as above.
The following lines describe the tree. The -th line of them contains two integers and which describe that the -th node is the parent node of the -th node, and the edge connecting the -th node and the -th node is endowed with a bitwise operator: if the operator is |; if the operator is &; and if the operator is ^.
Each of the following lines contains two integers and describing a query. It is guaranteed that the node is not a leaf in the tree.
Output Format
Output lines corresponding to given queries, the -th of which contains three integers representing the bitwise OR sum, the bitwise AND sum and the bitwise XOR sum for the -th query respectively.
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
Hint
In the sample case, the tree looks like
:::align{center}
:::
For the first query, the bitwise OR sum is .
For the second query, the bitwise OR sum is .