/ 
Time Limit: 2 sec / Memory Limit: 2048 MiB
配点 : 900 点
問題文
1 から N までの番号のついた N 頂点からなる重み付き木 T があります． T の i 番目の辺は頂点 A_i と頂点 B_i を結ぶ重み C_i の辺です．
今から T を元に，1 から N までの番号のついた N 頂点からなる完全無向グラフ G を作ります． G の各辺に対し，次のように容量を定めます．
- G の辺 (i,j) の容量は，T 上で頂点 i と頂点 j を結ぶパスに含まれる辺の重みの最小値とする．
G 上で頂点 i と頂点 j を分離する最小カットの容量を f(i,j) とします．
\sum_{1 \leq i < j \leq N} f(i,j) を 998244353 で割った余りを求めてください．
1 つの入力につき，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}
- 入力されるグラフは木である
- S ケースにわたる N の総和は 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 つ目のテストケースでは，G の辺 (1,2),(1,3),(2,3) の容量はそれぞれ 1,1,10 です． そして答えは f(1,2)+f(1,3)+f(2,3)=2+2+11=15 です．
Score : 900 points
Problem Statement
There is a weighted tree T with N vertices numbered 1 to N. The i-th edge of T connects vertices A_i and B_i with weight C_i.
We now construct a complete undirected graph G with N vertices numbered 1 to N, based on T. For each edge of G, the capacity is defined as follows.
- The capacity of edge (i,j) of G is the minimum weight of an edge contained in the path connecting vertices i and j on T.
Let f(i,j) be the capacity of the minimum cut separating vertices i and j on G.
Find \sum_{1 \leq i < j \leq N} f(i,j), modulo 998244353.
Solve S cases for each input.
Constraints
- 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}
- The input graph is a tree.
- The sum of N over the S cases is at most 250000.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
S case_1 case_2 \vdots case_S
Each test case is given in the following format:
N
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_{N-1} B_{N-1} C_{N-1}
Output
For each test case, output the answer.
Sample Input 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
Sample Output 1
15 32 13620068 909241492
In the first test case, the capacities of edges (1,2),(1,3),(2,3) of G are 1,1,10, respectively. The answer is f(1,2)+f(1,3)+f(2,3)=2+2+11=15.