33OJ
登录 注册

#P17807. [ICPC 2019 Nanchang R] Bitwise Tree

    ID: 20406 远端评测题 8000ms 512MiB 尝试: 0 已通过: 0 显示难度省选/NOI− 上传者: 标签>动态规划 DP2019树形 DPICPC

[ICPC 2019 Nanchang R] Bitwise Tree

Problem Description

You are given a tree with nn nodes labelled from 11 to nn, the root of which is the node labelled 11. Every node in the tree will be endowed with values related to given parameters a1,a2,⋯ ,ana_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)(u,v) indicating the uu-th and the vv-th node in the tree, the shortest path connecting them in the tree, denoted by

u=p0,p1,p2,⋯ ,ps−1,ps=vu=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)(u,v) given by

$$((a_{p_0}\ opt_1\ a_{p_1})\ opt_2\ a_{p_2})\cdots opt_s\ a_{p_s})$$

where optiopt_i is the operator on the edge between the node pi−1p_{i-1} and the node pip_i in this path.

Now you are given qq queries, each of which contains two integers dd and u (1≤u≤n)u~(1\le u\le n). For this query, the value of the ii-th node will be set to be (ai+i×d)(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)(u,v) where the uu-th node is an ancestor of the vv-th node. Note that a node is not considered as an ancestor of itself.

Input Format

The first line contains two integers n (2≤n≤105)n~(2 \le n \le 10^5) and q (1≤q≤105)q~(1\le q\le 10^5) indicating the size of the tree and the number of queries.

The second line contains nn integers a1,a2,⋯ ,an (1≤ai≤1018)a_1, a_2, \cdots, a_n~(1 \le a_i \le 10^{18}) described as above.

The following n−1n-1 lines describe the tree. The ii-th line of them contains two integers f (1≤f≤n)f~(1 \le f \le n) and s (0≤s≤2)s~(0 \le s \le 2) which describe that the ff-th node is the parent node of the (i+1)(i+1)-th node, and the edge connecting the (i+1)(i+1)-th node and the ff-th node is endowed with a bitwise operator: if s=0s=0 the operator is |; if s=1s=1 the operator is &; and if s=2s=2 the operator is ^.

Each of the following qq lines contains two integers d (0≤d≤100)d~(0\le d\le 100) and u (1≤u≤n)u~(1\le u\le n) describing a query. It is guaranteed that the node uu is not a leaf in the tree.

Output Format

Output qq lines corresponding to qq given queries, the ii-th of which contains three integers representing the bitwise OR sum, the bitwise AND sum and the bitwise XOR sum for the ii-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 (1∣2) ∣ ((1∣2)∣4) ∣ ((1∣2)&5) ∣ (1&3) = 7(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(2|4)~|~(2\&5)~=~6.