33OJ
登录 注册

#P17769. 「LDOI R2」数树术 / Vocaloid

    ID: 20438 远端评测题 1000~7000ms 512MiB 尝试: 0 已通过: 0 显示难度NOI/NOI+/CTS 上传者: 标签>洛谷原创O2优化洛谷月赛

「LDOI R2」数树术 / Vocaloid

Background

Problem Description

Miku gives you a tree with nn vertices, and the weight of vertex ii is aia_i.

Define the weight of a directed simple path u→vu \rightarrow v passing through kk vertices as follows: let the vertex weights on the path be b1,b2,⋯ ,bkb_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 mm 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 998244353998244353.

Note: φ(x)\varphi(x) is Euler's totient function, i.e., the number of positive integers less than or equal to xx that are coprime to xx.

Input Format

The first line contains two numbers n,mn,m.

The next line contains nn numbers, representing the vertex weights.

The next n−1n-1 lines each contain two numbers u,vu,v, representing an edge.

The next mm lines each contain two numbers u,vu,v, representing the query u→vu \to v for this directed simple path.

Output Format

Output mm lines, each representing the answer modulo 998244353998244353 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 bb Computation
1→21\to2 1,21,2 φ(φ(1)×2)=1\varphi(\varphi(1) \times 2)=1
2→32\to3 2,1,32,1,3 φ(φ(φ(2)×1)×3)=2\varphi(\varphi(\varphi(2) \times 1) \times 3)=2
3→43\to4 3,1,2,43,1,2,4 $\varphi(\varphi(\varphi(\varphi(3)\times 1)\times 2)\times 4)=2$
4→54\to5 4,2,54,2,5 φ(φ(φ(4)×2)×5)=4\varphi(\varphi(\varphi(4)\times 2)\times 5)=4
5→15\to1 5,2,15,2,1 φ(φ(φ(5)×2)×1)=2\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≤n,m \le ai≤a_i \le Score Time limit (s)
11 300300 10310^3 1515 11
22 8×1048 \times 10^4 1010 44
33 ^ 2020 1212 ^
44 5050 1313
55 2×1042 \times 10^4 200200 1515 77
66 8×1048 \times 10^4 ^ 1010 ^
77 2×1042 \times 10^4 10310^3 1515
88 8×1048 \times 10^4 ^ 1010

For all test cases, 1≤n,m≤8×1041 \le n,m \le 8 \times 10^4, 1≤ai≤1031 \le a_i \le 10^3.