#P7233. [2023省队模拟]情感

    ID: 7067 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3000省选/NOI-树形 DP换根 DPLCA树上倍增子树转区间差分树状数组普通线段树栈回滚维护状态贡献法

[2023省队模拟]情感

题目描述

给定一棵有 nn 个节点的树和 mm 条带权路径。三元组 (u,v,w)(u,v,w) 表示端点为 u,vu,v、权值为 ww 的路径。

对一个路径集合 SS,记 W(S)W(S) 为从 SS 中选取若干条两两没有公共点的路径能得到的最大权值之和。

设 UU 为给定的 mm 条路径构成的集合。对任意节点 u,vu,v,令 f(u,v)f(u,v) 等于使下式成立的最小非负整数 ww:

W(U∪{(u,v,w+1)})>W(U).W(U\cup\{(u,v,w+1)\})>W(U).

请计算 ∑u=1n∑v=1nf(u,v)\sum_{u=1}^n\sum_{v=1}^n f(u,v),结果对 998244353998244353 取模。

输入格式

第一行两个整数 n,mn,m,表示树的节点数和给定路径的条数。

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

接下来 mm 行,每行三个整数 u,v,wu,v,w,表示一条带权路径。

输出格式

输出一个整数表示答案。

样例输入

4 4
1 2
1 3
1 4
1 2 1
3 3 2
1 4 3
2 4 6

样例输出

100

样例中的 f(u,v)f(u,v) 如下,行和列分别对应 uu 和 vv。

1 2 3 4
1 6 6 8 6
2 3
3 8 2 8
4 6 8 5

数据范围与约定

对于全部数据,1≤n≤3×1051\le n\le3\times10^5,0≤m≤3×1050\le m\le3\times10^5,1≤w≤1091\le w\le10^9。

测试点 n,mn,m 特殊性质
1、2 10 无
3 40
4 150
5、6 350
7、8 1500
9、10 3499 树边满足 v=u+1v=u+1
11、12 3500 无
13、14 99995 给定路径均满足 u=vu=v
15、16 99996 给定路径均满足 w=1w=1
17、18 99997 树边满足 v=u+1v=u+1
19、20 99998 树边满足 u=1u=1
21、22、23 99999 树边满足 u=⌊v/2⌋u=\lfloor v/2\rfloor
24 10510^5 无
25 3×1053\times10^5