P12730 [KOI 2021 Round 2] 美食推荐

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

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$ 家餐厅的配送范围为： $$ R_i = \{ j \mid d(c_i, j) \leq d_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$ 家餐厅所在城市、配送距离上限与客户偏好度。

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

**约束条件** - 所有输入数据均为整数。 - $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 分）无额外约束条件。