#1682. 【模板】树链剖分
【模板】树链剖分
【模板】树链剖分
题目描述
标题: 【模板】树链剖分 - Problem - QOJ.ac
#5023. 【模板】树链剖分
The problem was used in the following contests:
请不要滥用评测资源。
给定一棵 n 个节点的树 T 以及树上的 m 条不同的路径 Ii=(ui,vi)(ui≠vi)。具体地,Ii 表示树上 ui 和 vi 之间的简单路径上所有点形成的点集。
考虑 T 上某条路径 I=(u,v),定义 f(I)=∑i=1m∑j=1m[Ii∪I=Ij∪I]。
对于 T 上所有不同路径 I,求 f(I) 之和,并将答案对 998244353 取模。也就是说,你需要求 (∑u=1n∑v=unf((u,v)))mod998244353。
输入格式
第一行一个整数 S,表示子任务编号。样例的子任务编号为 −1。
第二行两个整数 n,m,分别表示树的大小和路径条数。
接下来 n−1 行,每行两个整数 xi,yi 表示 T 上的一条边。
接下来 m 行,每行两个整数 ui,vi 表示第 i 条路径 Ii。
保证给定路径两两不同。
输出格式
输出一行一个整数表示答案。
样例一
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∼24 。注意评测子任务编号为实际子任务编号 +1 。
子任务编号模 5 的余数将子任务按数据大小划分。
- 若子任务编号模 5 余 0 ,则 n,m≤100 ,记为 A1$ 。
- 若子任务编号模 5 余 1 ,则 n,m≤500 ,记为 B1 。依赖于 A1 。
- 若子任务编号模 5 余 2 , 则 n,m≤1557 ,记为 C1 。依赖于 B1 。
- 若子任务编号模 5 余 3 ,则 n,m≤85500 ,记为 D1。依赖于 C1 。
- 若子任务编号模 5 余 4 ,则 n,m≤2×105 ,记为 E1 。依赖于 D1。
子任务编号除以 5 的商将子任务按特殊限制划分。
- 若子任务编号除以 5 商 0 ,则 T 是一条链,记为 A2。
- 若子任务编号除以 5 商 1 ,则 T 是一个菊花,记为 B2 。
- 若子任务编号除以 5 商 2 , 则所有路径端点互不相同,记为 C2。
- 若子任务编号除以 5 商 3 ,则所有路径以同一点为一端,记为 D2 。
- 若子任务编号除以 5 商 4 ,则无特殊限制,记为 E2 。 依赖于 A2,B2,C2,D2。
对于 100% 的数据, 2≤n≤2×105,1≤m≤min(n(n−1)2,2×105),1≤ui,vi,xi,yi≤n ,且所有 (xi,yi) 形成一棵树, 所有 Ii=(ui,vi) 互不相同, ui≠vi 。 各子任务分值如下表所示。
得分 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
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
-1
3 3
1 2
2 3
1 2
2 3
1 3
32
样例 2
-1
4 6
1 2
1 3
1 4
1 2
1 3
1 4
2 3
2 4
3 4
120