Inaho VIII

View as PDF

Points: 20
Time limit: 3.0s
Memory limit: 512M

Author:
Problem types

Inaho was thinking of a tree problem, when he came up with this rather beautiful problem!

Given a tree originally rooted at $$1$$ containing $$N$$ nodes each with a value $$v_i$$ and an arbitrary value $$K$$, support $$Q$$ of following operations:

• 1 R Reroot the tree so that node $$R$$ is the root.
• 2 a b Print the highest common ancestor of nodes $$a$$ and $$b$$.
• 3 a b Print the sum of all nodes' $$v_i$$ on the path from $$a$$ to $$b$$, inclusive.
• 4 a b Print the product of all nodes' $$v_i$$ on the path from $$a$$ to $$b$$, inclusive, modulo $$10^9+7$$.
• 5 a b Print the minimum of all nodes' $$v_i$$ on the path from $$a$$ to $$b$$, inclusive.
• 6 a b Print the maximum of all nodes' $$v_i$$ on the path from $$a$$ to $$b$$, inclusive.
• 7 a b Print the greatest common divisor of all nodes' $$v_i$$ on the path from $$a$$ to $$b$$, inclusive.
• 8 a b Print the bitwise AND of all nodes' $$v_i$$ on the path from $$a$$ to $$b$$, inclusive.
• 9 a b Print the bitwise OR of all nodes' $$v_i$$ on the path from $$a$$ to $$b$$, inclusive.
• 10 a b Print the bitwise XOR of all nodes' $$v_i$$ on the path from $$a$$ to $$b$$, inclusive.
• 11 a b Print the number of nodes whose $$v_i > K$$ on the path from $$a$$ to $$b$$, inclusive.
• 12 a b Print the number of nodes whose $$v_i < K$$ on the path from $$a$$ to $$b$$, inclusive.
• 13 a b Print the value $$v_i$$ that minimizes $$v_i - K$$, and $$v_i > K$$ of all nodes on the path from $$a$$ to $$b$$, inclusive. Print $$K$$ if there is no such node where $$v_i > K$$.
• 14 a b Print the value $$v_i$$ that minimizes $$K - v_i$$, and $$v_i < K$$ of all nodes on the path from $$a$$ to $$b$$, inclusive. Print $$K$$ if there is no such node where $$v_i < K$$.

It is guaranteed $$1 \le a, b, R \le N$$.

Input Specification

The first line will contain three space-separated integers, $$N, Q, K\ (1 \le N, Q \le 10^5, 1 \le K \le 1\ 000)$$, the number of nodes, the number of operations, and the arbitrary value $$K$$, respectively.

The second line will contain $$N$$ space-separated integers, $$v_1, v_2, \ldots, v_N\ (1 \le v_i \le 1\ 000)$$, the values of each node.

The next $$N-1$$ lines will each contain two space-separated integers, $$a, b\ (1 \le a, b \le N)$$, indicating that nodes $$a$$ and $$b$$ are connected by an edge. It is guaranteed the entire tree is connected.

The next $$Q$$ lines will each contain a valid operation as defined above.

Output Specification

For each operation that requires something to be outputted (everything except operation $$1$$), print the answer on its own line.

Sample Input

6 15 3
4 10 2 2 5 1
1 2
1 3
3 4
3 5
3 6
2 1 2
1 3
2 1 2
3 2 5
4 4 1
5 1 6
6 3 5
7 2 3
8 3 4
9 5 3
10 6 2
11 2 6
12 3 1
13 4 5
14 1 2

Sample Output

1
3
21
16
1
5
2
2
7
13
2
1
5
3