407737: GYM102888 L 子集大小和

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

L. 子集大小和time limit per test1.5 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

给定一棵 n 个节点的树,树上的每个节点 u 有一个颜色 wu

定义一个节点构成的集合 {u1, u2, ..., uk} 是「好的」,当且仅当这个集合内的所有节点颜色互不相同。特别的,空集合也是「好的」。

现在有 q 次查询,每次查询给出 u, v。令 uv 路径上的点组成的集合为 S,询问 S 的所有「好的」子集的大小之和。输出答案的时候对 998244353 取模。

Input

第一行包含两个整数 n, qn 表示树的大小,q 表示询问次数。保证 1 ≤ n, q ≤ 5 × 104

接下来一行包含 n 个空格分隔的整数,依次表示 w1, w2, ..., wn。保证 1 ≤ wi ≤ n

接下来 n - 1 行,每行包含两个整数 u, v,表示 uv 之间有一条边。保证 1 ≤ u, v ≤ n,且给出的是一棵树。

接下来 q 行,每一行包含两个整数 u, v,代表这次查询 uv 的路径。保证 1 ≤ u, v ≤ n

Output

输出 q 行,每行一个整数表示答案。

ExamplesInput
4 4
1 2 2 3
1 2
2 3
2 4
1 2
1 3
2 4
1 4
Output
4
7
4
12
Input
5 10
2 3 1 2 3
1 2
2 3
3 4
4 5
1 2
1 3
1 4
1 5
2 2
2 3
2 4
2 5
3 5
4 5
Output
4
12
20
33
1
4
12
20
12
4

加入题单

上一题 下一题 算法标签: