Inaho VIII

View as PDF

Submit solution

Points: 20
Time limit: 1.4s
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 the 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, \dots, 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

Comments

There are no comments at the moment.