#P17769. 「LDOI R2」数树术 / Vocaloid
「LDOI R2」数树术 / Vocaloid
Background
Problem Description
Miku gives you a tree with vertices, and the weight of vertex is .
Define the weight of a directed simple path passing through vertices as follows: let the vertex weights on the path be . Then the weight is $\varphi(\cdots \varphi(\varphi(\varphi(b_1) b_2) b_3) \cdots b_k)$.
There are queries. Each query gives a directed simple path, and you need to compute the weight of this path. Since the answer may be very large, you need to output the answer modulo .
Note: is Euler's totient function, i.e., the number of positive integers less than or equal to that are coprime to .
Input Format
The first line contains two numbers .
The next line contains numbers, representing the vertex weights.
The next lines each contain two numbers , representing an edge.
The next lines each contain two numbers , representing the query for this directed simple path.
Output Format
Output lines, each representing the answer modulo for one query.
5 5
1 2 3 4 5
1 2
1 3
2 4
2 5
1 2
2 3
3 4
4 5
5 1
1
2
2
4
2
7 3
1000 999 1000 999 1000 999 1000
1 2
2 3
3 4
4 5
5 6
6 7
2 7
1 6
1 7
804479352
83389870
941419136
12 12
58 359 579 955 963 436 125 74 303 643 813 767
1 2
1 3
2 4
2 5
3 6
2 7
2 8
5 9
4 10
8 11
8 12
11 3
9 4
7 2
2 1
10 7
4 4
4 12
2 9
1 4
2 4
1 11
5 12
742391805
664076287
14320
9968
656179200
760
564461568
10982400
1082240
135280
27371520
564461568
Hint
Explanation
For Sample 1:
| Query | Vertex weight sequence | Computation |
|---|---|---|
| $\varphi(\varphi(\varphi(\varphi(3)\times 1)\times 2)\times 4)=2$ | ||
Therefore, the output is 1 2 2 4 2 in order.
Constraints
This problem uses subtask scoring.
| Subtask | Score | Time limit (s) | ||
|---|---|---|---|---|
| ^ | ^ | |||
| ^ | ^ | |||
| ^ | ||||
For all test cases, , .