← 返回题目列表

AtCoder · awtf2026algo_a

A. 最小重量图的最小切割

中文机器翻译题面 查看原题

分数: 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.