P17769 「LDOI R2」数树术 / Vocaloid


Miku gives you a tree with $n$ vertices, and the weight of vertex $i$ is $a_i$. Define the weight of a **directed** simple path $u \rightarrow v$ passing through $k$ vertices as follows: let the vertex weights on the path be $b_1, b_2, \cdots, b_k$. Then the weight is $\varphi(\cdots \varphi(\varphi(\varphi(b_1) b_2) b_3) \cdots b_k)$. There are $m$ 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 $998244353$. Note: $\varphi(x)$ is Euler's totient function, i.e., the number of positive integers less than or equal to $x$ that are coprime to $x$.

The first line contains two numbers $n,m$. The next line contains $n$ numbers, representing the vertex weights. The next $n-1$ lines each contain two numbers $u,v$, representing an edge. The next $m$ lines each contain two numbers $u,v$, representing the query $u \to v$ for this **directed** simple path.

Output $m$ lines, each representing the answer modulo $998244353$ for one query.

### Explanation For Sample 1: | Query | Vertex weight sequence $b$ | Computation | |:-:|:-:|:-:| | $1\to2$ | $1,2$ | $\varphi(\varphi(1) \times 2)=1$ | | $2\to3$ | $2,1,3$ | $\varphi(\varphi(\varphi(2) \times 1) \times 3)=2$ | | $3\to4$ | $3,1,2,4$ | $\varphi(\varphi(\varphi(\varphi(3)\times 1)\times 2)\times 4)=2$ | | $4\to5$ | $4,2,5$ | $\varphi(\varphi(\varphi(4)\times 2)\times 5)=4$ | | $5\to1$ | $5,2,1$ | $\varphi(\varphi(\varphi(5)\times 2)\times 1)=2$ | Therefore, the output is `1 2 2 4 2` in order. ### Constraints **This problem uses subtask scoring.** | Subtask | $n,m \le$ | $a_i \le$ | Score | Time limit (s) | |:-:|:-:|:-:|:-:|:-:| | $1$ | $300$ | $10^3$ | $15$ | $1$ | | $2$ | $8 \times 10^4$ | $10$ | $10$ | $4$ | | $3$ | ^ | $20$ | $12$ | ^ | | $4$ | ^ | $50$ | $13$ | ^ | | $5$ | $2 \times 10^4$ | $200$ | $15$ | $7$ | | $6$ | $8 \times 10^4$ | ^ | $10$ | ^ | | $7$ | $2 \times 10^4$ | $10^3$ | $15$ | ^ | | $8$ | $8 \times 10^4$ | ^ | $10$ | ^ | For all test cases, $1 \le n,m \le 8 \times 10^4$, $1 \le a_i \le 10^3$.