Background

就是一个裸的可持久化动态仙人掌维护最小费用无源汇有上下界可行流再套上拓展 9 模数广义分治 FFT

Description

给一棵有n个节点且有边权的树（1为根），对于所有 $x,y[x≠y]$ 求 $dist(x,y)$ 的和 $\mod 998244353$
$dist(i,j)$ 指节点i和节点j的最短距离

Format

Input

第 $1$ 行：$n$
第 $2$ 至 $n$ 行：三个数 $u,v,w$ ，表示u到v有一条长度为w的边

Output

输出 $ans \mod 998244353$

Sample 1

Input

3
1 2 1000
1 3 2000

Output

12000

Limitation

对于40%的数据，$1<=n<=100$
对于100%的数据，$1<=n<=200000,w<=10000$
$500ms$ for each test case.

Source

@zyc Original