MooTube

题目描述

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

输入格式

第一行输入包含 $N$ 和 $Q$（$1 \leq Q \leq 100,000$）。 接下来的 $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$ 行描述农夫 John 的 $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

提示

农夫 John 发现：视频 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。 农夫 John 想知道：当 $K=1$ 时从视频 2 出发会推荐多少视频；当 $K=3$ 时从视频 1 出发会推荐多少视频；当 $K=4$ 时从视频 1 出发会推荐多少视频。我们看到，当 $K=1$ 时，会在视频 2 上推荐视频 1、3 和 4。当 $K=4$ 时，从视频 1 不会推荐任何视频。而当 $K=3$ 时，会从视频 1 推荐视频 2 和 4。 题目鸣谢：Jay Leeds

标签: USACO|2018|Gold

来源

USACO|2018|Gold