#P7233. [2023省队模拟]情感
[2023省队模拟]情感
题目描述
给定一棵有 个节点的树和 条带权路径。三元组 表示端点为 、权值为 的路径。
对一个路径集合 ,记 为从 中选取若干条两两没有公共点的路径能得到的最大权值之和。
设 为给定的 条路径构成的集合。对任意节点 ,令 等于使下式成立的最小非负整数 :
请计算 ,结果对 取模。
输入格式
第一行两个整数 ,表示树的节点数和给定路径的条数。
接下来 行,每行两个整数 ,表示树的一条边。
接下来 行,每行三个整数 ,表示一条带权路径。
输出格式
输出一个整数表示答案。
样例输入
4 4
1 2
1 3
1 4
1 2 1
3 3 2
1 4 3
2 4 6
样例输出
100
样例中的 如下,行和列分别对应 和 。
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 6 | 6 | 8 | 6 |
| 2 | 3 | |||
| 3 | 8 | 2 | 8 | |
| 4 | 6 | 8 | 5 | |
数据范围与约定
对于全部数据,,,。
| 测试点 | 特殊性质 | |
|---|---|---|
| 1、2 | 10 | 无 |
| 3 | 40 | |
| 4 | 150 | |
| 5、6 | 350 | |
| 7、8 | 1500 | |
| 9、10 | 3499 | 树边满足 |
| 11、12 | 3500 | 无 |
| 13、14 | 99995 | 给定路径均满足 |
| 15、16 | 99996 | 给定路径均满足 |
| 17、18 | 99997 | 树边满足 |
| 19、20 | 99998 | 树边满足 |
| 21、22、23 | 99999 | 树边满足 |
| 24 | 无 | |
| 25 |