#1488. 人造情感

人造情感

题目描述

“这个任务永远无法完成。我不会再重复同样的错误。”
“懂得了爱与情感的他,早已经不是机器人了……从这个角度上看,3000A 就是你的儿子,霍星。”
—— 永别,3000A!《魔角侦探》

给你一颗 nn 个节点的树,以及 mm 条路径 (u,v,w)(u, v, w),其中 ww 可以认为是 (u,v)(u, v) 这题路径被标记的一个权值。一个路径集合 SS 的重量 W(S)W(S) 记为:找出 SS 的一个权值之和最大的子集,该子集满足任何两条路径没有公共点,这个子集的所有路径权值之和就是 W(S)W(S)

f(u,v)=wf(u, v) = w 为最小的非负整数 ww,使得对于给定的 mm 条边组成的路径集合 UUW(U{(u,v,w+1)})>W(U)W(U \cup \{(u, v, w + 1)\}) > W(U)

请你计算下式,对 998244353998244353 取模。

u=1nv=1nf(u,v)\sum_{u=1}^n \sum_{v=1}^n f(u, v)

输入格式

第一行输入两个整数 n,mn, m,表示树的节点数量以及给出的路径数量。

接下来 n1n-1 行,每行输入两个整数 u,vu, v 表示树的一条边。

接下来 mm 行,每行输入三个整数 u,v,wu, v, w,表示在集合中加入这条 u,vu, 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)=6f(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)=6f(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)=8f(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)=5f(4, 1) = 6, f(4, 2) = 6, f(4, 3) = 8, f(4, 4) = 5

数据范围与提示

对于 100%100\% 的数据,保证 $1\le n\le 3\times 10^5, 0\le m\le 3\times 10^5, 1\le w\le 10^9$。

测试点 n,mn,m 特殊性质
1,21,2 =10=10
33 =40=40
44 =150=150
5,65,6 =350=350
7,87,8 =1,500=1,500
9,109,10 =3,499=3,499 树的结构 v=u+1v=u+1
11,1211,12 =3,500=3,500
13,1413,14 =99,995=99,995 给出的路径 u=vu=v
15,1615,16 =99,996=99,996 给出的路径 w=1w=1
17,1817,18 =99,997=99,997 树的结构 v=u+1v=u+1
19,2019,20 =99,998=99,998 树的结构 u=1u=1
21,22,2321,22,23 =99,999=99,999 树的结构 u=v/2u = \lfloor v/2\rfloor
2424 =105=10^5
2525 =3×105=3\times10^5