节点距离
Background
就是一个裸的可持久化动态仙人掌维护最小费用无源汇有上下界可行流再套上拓展 9 模数广义分治 FFT
Description
给一棵有n个节点且有边权的树(1为根),对于所有\(x,y(x≠y)\)求\(dist(x,y)\)的和%998244353
\(dist(i,j)\)指节点i和节点j的最短距离
Format
Input
第\(1\)行:\(n\)
第\(2至n\)行:三个数\(u,v,w\),表示u到v有一条长度为w的边
Output
输出\(ans\)%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