题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

KOI 国有 $N$ 个城市。每个城市编号从 1 到 $N$。

KOI 国的结构很特别，把城市看作图的顶点、道路看作无向边，则这个国家的结构可以表示为一个包含 $N$ 个顶点的树。树是一个无环的连通图。

KOI 国共有 $M$ 家美食餐厅，每家餐厅编号从 1 到 $M$。某些城市可能没有餐厅，也可能有两个以上的餐厅，请特别注意这一点。

第 $i$ 家餐厅（$1 \leq i \leq M$）位于城市 $c_i$，配送范围为距离不超过 $d_i$ 的城市，且其客户偏好度为 $g_i$。

第 $i$ 家餐厅可以向从城市 $c_i$ 出发，经过至多 $d_i$ 条道路所能到达的所有城市配送。即，第 $i$ 家餐厅的配送范围为：

其中，$d(a, b)$ 表示从城市 $a$ 到城市 $b$ 之间的最短路径长度（即需要经过的最少道路数）。

你是一名外卖推荐平台的运营者。为了避免服务重叠，你希望从 $M$ 家餐厅中选出一个子集 $S$，满足以下条件：

• 对于任意城市 $p$，它不能同时被 $S$ 中的两个或多个餐厅包含在其配送范围内。也就是说，对于 $S$ 中任意不同的两家餐厅 $i$ 和 $j$，都有 $R_i \cap R_j = \emptyset$。

请从所有满足上述条件的子集 $S$ 中，选出客户偏好度总和最大的一个，并输出该最大值。

输入格式

第一行包含两个整数 $N$ 和 $M$，中间用一个空格分隔。

接下来的 $N-1$ 行中，每行包含两个整数 $a$ 和 $b$，表示城市 $a$ 和城市 $b$ 之间有一条道路相连。

接下来的 $M$ 行中，每行包含三个整数 $c_i$、$d_i$ 和 $g_i$，表示第 $i$ 家餐厅所在城市、配送距离上限与客户偏好度。

输出格式

输出一个整数，表示满足条件的餐厅集合中客户偏好度之和的最大值。

8 5
1 2
2 3
3 4
4 5
5 6
4 7
4 8
3 2 40
6 0 5
8 0 5
2 1 16
5 1 32

53

提示

约束条件

• 所有输入数据均为整数。
• $1 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• 对于所有 $i$（$1 \leq i \leq M$），满足 $0 \leq d_i \leq N - 1$，$1 \leq g_i \leq 10^9$

子任务

1. （9 分）对于 $1 \leq i \leq N - 1$，城市 $i$ 与城市 $i+1$ 之间有一条道路相连。
2. （11 分）$N, M \leq 20$
3. （17 分）$N, M \leq 2\,000$
4. （10 分）$N \leq 2\,000$
5. （8 分）对于 $2 \leq i \leq N$，城市 $\lfloor i/2 \rfloor$ 与城市 $i$ 之间有一条道路相连。
6. （12 分）图中度数大于等于 3 的顶点最多只有一个。
7. （33 分）无额外约束条件。