MooTube

题目描述:

在业余时间，Farmer John创建了一个新的视频分享服务，他命名为MooTube。

在MooTube上，FJ的奶牛可以录制、分享和发现许多有趣的视频(中国俗语-抖音)。他的奶牛已经发布 N 个视频，编号为1到N（第i头奶牛所发布的视频编号为i）。然而，FJ无法弄清楚如何帮助他的奶牛找到她们可能喜欢的新视频。

FJ希望为每个MooTube视频创建一个"推荐视频"列表。这样，奶牛将被推荐与她们已经观看的视频最相关的视频。

FJ设计了一个“相关性”指标，正如名称所示，它决定了两个视频对彼此的相关程度。他选择 N-1 对视频并手动计算其配对相关性。然后，FJ将他的视频抽象化为一个网络，其中每个视频都抽象成一个结点，N-1 对视频初始时已全部连接。然后FJ选择了他的N-1对视频，这样任何视频都可以通过一条连接路径互相关联。FJ决定将任何一对视频的相关性定义为沿着这条路径的任何连接的最小相关性值。

FJ想挑选一个特定值 K，以便在任何给定的MooTube视频，与某个结点相连的路径上相关性值不低于 K 的所有其他视频都将被推荐。然而，FJ担心会有太多的视频被推荐给他的奶牛，这会影响他的奶牛的产奶量！因此，他需要细心设定一个合适的特定值。Farmer John希望你能够帮他回答关于某些特定值的推荐视频的一些问题。

输入格式:

第 1 行输入包含两个整数N和Q；

接下来 N-1 行分别描述FJ手动比较的一对视频，每行包含三个整数P_i，Q_i和 R_i；表明视频P_i和 Q_i之间的相关性值是R_i；

接下来 Q 行描述FJ的问题，每行包含两个整数，K_i和V_i，表明FJ的问题是问有多少个视频会被推荐给编号为V_i的奶牛。

输出格式:

输出共 Q 行，第i行输出推荐给编号为V_i奶牛的视频个数；

样例输入:

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

样例输出:

3
0
2

提示:

【样例解释】样例如上图，其中黑色的圆点代表视频编号（同时也是奶牛的编号），红色的数字代表两个视频之间的相关性值；

对于询问①1 2：与编号为2的奶牛的视频相连的视频编号是1,3,4；直接相连且每个视频的相关性值都大于给定的数值1，所以这3个视频都将推荐给编号为2的奶牛；

对于询问②4 1：与编号为1的奶牛的视频相连的视频编号是2,3,4；其中编号为2的视频直连，视频的相关性值为3小于4；编号为3的视频与奶牛1间接相连，此时应该取路径中相关性值最小的2小于4；同样编号为4的视频与1相连，路径中的相关性值最小为3小于4；所以此时没有视频推荐给编号为1的奶牛；

对于询问③3 1：编号为2的视频和编号为4的视频将被推荐给编号为1的奶牛；

【数据规模】

对于20%的数据： 1≤N，Q≤200；

对于60%的数据： 1≤N，Q≤5,000；

对于100%的数据： 1≤N，Q≤100,000；1≤V_i≤N；1≤P_i≠Q_i≤N；1≤R_i，K_i≤1,000,000,000；

时间限制: 1000ms
空间限制: 128MB

---

来源: Usaco2018 Jan Gold