MooTube

题目描述

在空闲时间里，农夫约翰创建了一个新的视频分享服务，名为 MooTube。在 MooTube 上，农夫约翰的奶牛可以录制、分享并发现许多有趣的视频。奶牛们已经发布了 $N$ 个视频（$1 \leq N \leq 5000$），方便起见编号为 $1 \ldots N$。然而，FJ 还不太清楚如何帮助奶牛们找到可能喜欢的新视频。 FJ 想为每个 MooTube 视频创建一份“推荐视频”列表。这样，奶牛们将会被推荐与她们已经观看的视频最相关的视频。 FJ 设计了一个“相关度（relevance）”度量，用于（顾名思义）衡量两个视频之间的相关程度。他选取了 $N-1$ 对视频，并手动计算了它们两两之间的相关度。随后，FJ 将这些视频可视化为一个网络：每个视频是一个节点，而他手动考虑的这 $N-1$ 对视频之间各连一条边。方便的是，FJ 选择这 $N-1$ 对的方式使得任意一个视频都能通过这些连接以且仅以一种方式到达任意另一个视频。FJ 决定：任意一对视频的相关度定义为它们之间这条路径上所有连接相关度的最小值。 农夫约翰想选定一个值 $K$，使得对于任意给定的 MooTube 视频，所有与该视频相关度至少为 $K$ 的其他视频都会被推荐。然而，FJ 担心推荐的视频太多会分散奶牛们的注意力，从而影响产奶！因此，他希望谨慎设置一个合适的 $K$。农夫约翰希望你能帮助回答若干个关于在某些 $K$ 值下推荐视频数量的问题。

输入格式

第一行输入包含 $N$ 和 $Q$（$1 \leq Q \leq 5000$）。 接下来的 $N-1$ 行每行描述一对 FJ 手动比较的视频。每行包含三个整数 $p_i$、$q_i$ 和 $r_i$（$1 \leq p_i, q_i \leq N, 1 \leq r_i \leq 1,000,000,000$），表示视频 $p_i$ 和 $q_i$ 之间有一条相关度为 $r_i$ 的连接。 接下来的 $Q$ 行描述农夫约翰的 $Q$ 个问题。每行包含两个整数 $k_i$ 和 $v_i$（$1 \leq k_i \leq 1,000,000,000, 1 \leq v_i \leq N$），表示 FJ 的第 $i$ 个问题询问：当 $K = k_i$ 时，观看视频 $v_i$ 的观众会被推荐多少个视频。

输出格式

输出 $Q$ 行。第 $i$ 行输出 FJ 第 $i$ 个问题的答案。

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

3
0
2

提示

农夫约翰发现：视频 1 和 2 的相关度为 3，视频 2 和 3 的相关度为 2，视频 2 和 4 的相关度为 4。基于此，视频 1 和 3 的相关度为 min(3, 2) = 2，视频 1 和 4 的相关度为 min(3, 4) = 3，视频 3 和 4 的相关度为 min(2, 4) = 2。 农夫约翰想知道：从视频 2 出发在 $K=1$ 时会推荐多少视频；从视频 1 出发在 $K=3$ 时会推荐多少视频；以及从视频 1 出发在 $K=4$ 时会推荐多少视频。可以看出，当 $K=1$ 时，会在视频 2 旁推荐视频 1、3 和 4。当 $K=4$ 时，从视频 1 不会推荐任何视频。而当 $K=3$ 时，会从视频 1 推荐视频 2 和 4。 题目鸣谢：Jay Leeds

标签: USACO|2018|Silver

来源

USACO|2018|Silver