请不要滥用评测资源。
给定一棵 n 个节点的树 T 以及树上的 m 条不同的路径 Ii=(ui,vi)(ui≠vi)。具体地,Ii 表示树上 ui 和 vi 之间的简单路径上所有点形成的点集。
考虑 T 上某条路径 I=(u,v),定义 f(I)=m∑i=1m∑j=1[Ii∪I=Ij∪I]。
对于 T 上所有不同路径 I,求 f(I) 之和,并将答案对 998244353 取模。也就是说,你需要求 (n∑u=1n∑v=uf((u,v)))mod。
输入格式
第一行一个整数 S,表示子任务编号。样例的子任务编号为 −1。
第二行两个整数 n,m,分别表示树的大小和路径条数。
接下来 n−1 行,每行两个整数 x_i,y_i 表示 T 上的一条边。
接下来 m 行,每行两个整数 u_i,v_i 表示第 i 条路径 I_i。
保证给定路径两两不同。
输出格式
输出一行一个整数表示答案。
样例一
input
-1
3 3
1 2
2 3
1 2
2 3
1 3
output
32
样例二
input
-1
4 6
1 2
1 3
1 4
1 2
1 3
1 4
2 3
2 4
3 4
output
120
样例三
input
-1
7 7
1 2
1 3
2 4
4 5
5 6
5 7
5 7
3 1
4 7
7 1
2 6
3 6
3 5
output
330
数据范围
本题采用捆绑测试,共 25 个子任务,分别编号为 0 \sim 24 。注意评测子任务编号为实际子任务编号 +1 。
子任务编号模 5 的余数将子任务按数据大小划分。
- 若子任务编号模 5 余 0 ,则 n, m \leq 100 ,记为 A1$ 。
- 若子任务编号模 5 余 1 ,则 n, m \leq 500 ,记为 B1 。依赖于 A1 。
- 若子任务编号模 5 余 2 , 则 n, m \leq 1557 ,记为 C1 。依赖于 B1 。
- 若子任务编号模 5 余 3 ,则 n, m \leq 85500 ,记为 D1。依赖于 C1 。
- 若子任务编号模 5 余 4 ,则 n, m \leq 2 \times 10^5 ,记为 E1 。依赖于 D1。
子任务编号除以 5 的商将子任务按特殊限制划分。
- 若子任务编号除以 5 商 0 ,则 T 是一条链,记为 A2。
- 若子任务编号除以 5 商 1 ,则 T 是一个菊花,记为 B2 。
- 若子任务编号除以 5 商 2 , 则所有路径端点互不相同,记为 C2。
- 若子任务编号除以 5 商 3 ,则所有路径以同一点为一端,记为 D2 。
- 若子任务编号除以 5 商 4 ,则无特殊限制,记为 E 2 。 依赖于 A2,B2,C2,D2。
对于 100 \% 的数据, 2 \leq n \leq 2 \times 10^5 , 1 \leq m \leq \min \left(\frac{n(n-1)}{2}, 2 \times 10^5\right) , 1 \leq u_i, v_i, x_i, y_i \leq n ,且所有 \left(x_i, y_i\right) 形成一棵树, 所有 I_i=\left(u_i, v_i\right) 互不相同, u_i \neq v_i 。 各子任务分值如下表所示。
得分 | A1 | B1 | C1 | D1 | E1 | 总和 |
---|---|---|---|---|---|---|
A2 | 11 | 22 | 33 | 77 | 77 | 2020 |
B2 | 11 | 22 | 33 | 44 | 44 | 1414 |
C2 | 11 | 22 | 55 | 77 | 77 | 2222 |
D2 | 11 | 33 | 55 | 44 | 55 | 1818 |
E2 | 22 | 33 | 33 | 99 | 99 | 2626 |
总和 | 66 | 1212 | 1919 | 3131 | 3232 | 100100 |