题目描述
“这个任务永远无法完成。我不会再重复同样的错误。”
“懂得了爱与情感的他,早已经不是机器人了……从这个角度上看,3000A 就是你的儿子,霍星。”
—— 永别,3000A!《魔角侦探》
给你一颗 n 个节点的树,以及 m 条路径 (u,v,w),其中 w 可以认为是 (u,v) 这题路径被标记的一个权值。一个路径集合 S 的重量 W(S) 记为:找出 S 的一个权值之和最大的子集,该子集满足任何两条路径没有公共点,这个子集的所有路径权值之和就是 W(S)。
记 f(u,v)=w 为最小的非负整数 w,使得对于给定的 m 条边组成的路径集合 U,W(U∪{(u,v,w+1)})>W(U) 。
请你计算下式,对 998244353 取模。
u=1∑nv=1∑nf(u,v)
输入格式
第一行输入两个整数 n,m,表示树的节点数量以及给出的路径数量。
接下来 n−1 行,每行输入两个整数 u,v 表示树的一条边。
接下来 m 行,每行输入三个整数 u,v,w,表示在集合中加入这条 u,v 为端点的路径以及其权值。
输出格式
输出一个整数表示答案。
样例
4 4
1 2
1 3
1 4
1 2 1
3 3 2
1 4 3
2 4 6
100
f(1,1)=6,f(1,2)=6,f(1,3)=8,f(1,4)=6
f(2,1)=6,f(2,2)=3,f(2,3)=8,f(2,4)=6
f(3,1)=8,f(3,2)=8,f(3,3)=2,f(3,4)=8
f(4,1)=6,f(4,2)=6,f(4,3)=8,f(4,4)=5
数据范围与提示
对于 100% 的数据,保证 $1\le n\le 3\times 10^5, 0\le m\le 3\times 10^5, 1\le w\le 10^9$。
测试点 |
n,m |
特殊性质 |
1,2 |
=10 |
|
3 |
=40 |
4 |
=150 |
5,6 |
=350 |
7,8 |
=1,500 |
9,10 |
=3,499 |
树的结构 v=u+1 |
11,12 |
=3,500 |
|
13,14 |
=99,995 |
给出的路径 u=v |
15,16 |
=99,996 |
给出的路径 w=1 |
17,18 |
=99,997 |
树的结构 v=u+1 |
19,20 |
=99,998 |
树的结构 u=1 |
21,22,23 |
=99,999 |
树的结构 u=⌊v/2⌋ |
24 |
=105 |
|
25 |
=3×105 |