题目描述

coco 有一颗树，它有 n 个顶点，顶点编号为 1 - n，树有 m 条链，每条链有一个重量。coco 想选择一些不想交不重合的链组合（两条链不同，并且没有公共点），求其最大重量和。

输入格式

第一行两个正整数 n, m；
接下来 n - 1 行，每行两个整数 ai, bi，表示顶点 ai 到顶点 bi 有边；
接下来 m 行，每行三个整数 u, v, val，表示顶点 u 到顶点 v 的链重 val。

输出格式

一个整数，选择链的最大重量和。

样例输入

7 3
1 2
1 3
2 4
2 5
3 6
3 7
2 3 4
4 5 3
6 7 3

样例输出

6

数据范围

对于 30%的数据，1 < n, m <= 100，1 <= ai, bi <= n，1 <= u, v <= n，0 < val < 100；
对于 100%的数据，1 < n, m <= 100000，1 <= ai, bi <= n，1 <= u, v <= n，0 < val < 1000。

限制

1s

来源

CWOI新高二专题测试十一