AT_AGC_A （最新）English

Lag_longlong

2026-07-10 21:12:19

发布于：广东

14阅读

0回复

0点赞

~~和正式题目略有不同，可忽略不计~~

AT_AGC_A - Min Cut of Graph of Min Weight

Score: 900 points

Problems Statement

There is a weighted tree $\bm{T}$ with $\bm{N}$ vertices numbered 1 to $\bm{N}$ .The i-th edge of T connects vertices $A_i$ and $B_i$ with weight $C_i$ .

We now construct a complete indirected gragh $\bm{C}$ with $\bm{N}$ vertices numbered 1 to $\bm{N}$ , based on $\bm{T}$ . For each edge of $\bm{G}$ , the capacity is defined as follows.

The capacity of edge

(i,j) of $\bm{G}$ is the minimum weight of an edge contained in the path connecting vertices i and j on $\bm{T}$ .

Let f(i,j) be the capacity of the minimumcut separating vertices i and j on $\bm{G}$ .

Find $∑_(1≤i<j≤N)$ · $\bm{F}$ (i,j) , modulo 998244353.

Solve $\bm{S}$ cases for each input.

Constraints

1 ≤ $\bm{S}$ ≤ 125000
2 ≤ $\bm{N}$ ≤ 250000
1 ≤ $A_i$ , $B_i$ ≤N
1 ≤ $C_ i$ ≤ $10^{12}$
The input graph is a tree.
The sum of $\bm{N}$ over the $\bm{S}$ cases is at most 250000.
All input values are integers.

Input

The input is given from Standard Input in the following format:

$S \\ \text{case } 1 \\ \text{case } 2 \\ \vdots \\ \text{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

Explanation

In the first test case, the capacities of edges (1,2)$, $(1,3)$ , and $(2,3) of $\bm{G}$ are $1$ , $1$ , and $10$ , respectively. The answer is:
$f(1,2) + f(1,3) + f(2,3) = 2 + 2 + 11 = 15$