QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 1024 MB Total points: 100
[-7]
统计

请不要滥用评测资源。

给定一棵 n 个节点的树 T 以及树上的 m 条不同的路径 Ii=(ui,vi)(uivi)。具体地,Ii 表示树上 uivi 之间的简单路径上所有点形成的点集。

考虑 T 上某条路径 I=(u,v),定义 f(I)=mi=1mj=1[IiI=IjI]

对于 T 上所有不同路径 I,求 f(I) 之和,并将答案对 998244353 取模。也就是说,你需要求 (nu=1nv=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