Inaho VIII

View as PDF

Submit solution

All submissions

Best submissions

Points: 20

Time limit: 1.4s

Memory limit: 512M

Author:

Ninjaclasher

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$ $1$ containing $N$ $N$ nodes each with a value $v_i$ $v_{i}$ and an arbitrary value $K$ $K$ , support $Q$ $Q$ of the following operations:

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

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

Input Specification

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

The second line will contain $N$ $N$ space-separated integers, $v_1, v_2, \dots, v_N$ $v_{1}, v_{2}, \dots, v_{N}$ $(1 \le v_i \le 1\,000)$ $(1 \leq v_{i} \leq 1 000)$ , the values of each node.

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

The next $Q$ $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$ $1$ ), print the answer on its own line.

Sample Input

Copy

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

Copy

Comments

There are no comments at the moment.