分数: 900 点
问题陈述
有一棵加权树 T 与 N 顶点编号 1 to N。 的 i第边缘 T 连接顶点 A_i 和 B_i 有重量 C_i.
我们现在构建一个完整的无向图 G 与 N 顶点编号 1 to N,基于 T。 对于每条边 G,容量定义如下。
- 边缘容量 (i,j) of G 是连接顶点的路径中包含的边的最小权重 i 和 j on T.
让 f(i,j) 是最小割分离顶点的容量 每个输入的 i 和 j on G.
查找 \sum_{1 \leq i < j \leq N} f(i,j),模数 998244353.
解决 S 例。
约束
- 1 \leq S \leq 125000
- 2 \leq N \leq 250000
- 1 \leq A_i,B_i \leq N
- 1 \leq C_i \leq 10^{12}
- 输入图是一棵树。
- 总和 N 超过 S 案例最多 250000.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
S case_1 case_2 \vdots case_S
每个测试用例均按以下格式给出:
N
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_{N-1} B_{N-1} C_{N-1}
输出
对于每个测试用例,输出答案。
示例输入 1
4 3 1 2 1 2 3 10 4 1 2 1 2 3 10 3 4 2 13 11 4 337329830 13 1 72247 4 1 1768959 5 4 5399893 2 8 1832265 12 7 107755 10 4 743 5 12 95 4 3 389684075 2 6 1222 11 8 253280162722 9 4 21671 15 8 5 285187324995 14 10 755031423304 2 8 88860861719 12 7 596982637940 10 4 225447687713 7 15 210989590191 13 5 836365489027 6 15 859904883890 8 1 362117197524 12 8 422952343663 1 14 112179584332 15 11 487330735107 12 9 528451854379 3 7 343910842803
示例输出 1
15 32 13620068 909241492
在第一个测试用例中,边的容量 分别为 (1,2),(1,3),(2,3) of G 是 1,1,10。 答案是 f(1,2)+f(1,3)+f(2,3)=2+2+11=15.