AT_awtf2026algo_a Min Cut of Graph of Min Weight

有一棵带权重的树 $T$，包含 $N$ 个编号为 $1$ 到 $N$ 的节点。$T$ 的第 $i$ 条边连接节点 $A_i$ 和 $B_i$，权重为 $C_i$。 现在基于 $T$ 构造一个完全无向图 $G$，有 $N$ 个编号为 $1$ 到 $N$ 的点。对于 $G$ 的每一条边，其容量定义如下： - $G$ 中边 $(i,j)$ 的容量等于 $T$ 上连接节点 $i$ 和 $j$ 的路径中权重的最小值。 记 $f(i,j)$ 表示 $G$ 上将点 $i$ 和 $j$ 分开的最小割的容量。 求 $\sum_{1 \leq i < j \leq N} f(i,j)$，结果对 $998244353$ 取模。 对每组输入，求解 $S$ 组测试数据。

从标准输入读入。 > $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 对于第一个测试用例，$G$ 中边 $(1,2)$、$(1,3)$、$(2,3)$ 的容量分别是 $1$、$1$、$10$。答案为 $f(1,2)+f(1,3)+f(2,3)=2+2+11=15$。 ### 数据范围 - $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$。 - 所有输入值均为整数。 由 ChatGPT 5 翻译