#1962. milimili (゜-゜)つロ 干杯~

milimili (゜-゜)つロ 干杯~

题目描述

在业余时间 面条老师 创建了一个新的视频共享服务,他将其命名为 milimili。在 milimili 上 面条老师 的朋友可以录制,分享和发现许多有趣的视频。他的朋友已经发布了 NN 个视频(1N50001 \leq N \leq 5000),为了方便将其编号为 1N1 \ldots N 。然而,面条老师 无法弄清楚如何帮助他的朋友找到他们可能喜欢的新视频。

面条老师 希望为每个 milimili 视频创建一个“推荐视频”列表。这样,朋友将被推荐与他们已经观看过的视频最相关的视频。

面条老师 设计了一个“相关性”度量标准,顾名思义,它确定了两个视频相互之间的相关性。他选择 N1N-1 对视频并手动计算其之间的相关性。然后,面条老师 将他的视频建成一棵树,其中每个视频是节点,并且他手动将 N1N-1 对视频连接。为了方便,面条老师 选择了 N1N-1 对,这样任意视频都可以通过一条连通路径到达任意其他视频。 面条老师 决定将任意一对视频的相关性定义为沿此路径的任何连接的最小相关性。 面条老师 想要选择一个 KK 值,以便在任何给定的 milimili 视频旁边,推荐所有其他与该视频至少有 KK 相关的视频。然而,面条老师 担心会向他的朋友推荐太多的视频,这可能会分散他们工作的注意力!因此,他想设定适当的 KK 值。 面条老师希望得到您的帮助,回答有关 KK 值的推荐视频的一些问题。

输入格式

第一行输入包含 NNQQ1Q50001 \leq Q \leq 5000)。

接下来的 N1N-1 行描述了 面条老师 手动比较的一对视频。 每行包括三个整数 pip_iqiq_irir_i1pi,qiN1 \leq p_i, q_i \leq N1ri1091 \leq r_i \leq 10^9),表示视频 pip_iqiq_i 已连接并且相关性为 rir_i

接下来的 QQ 行描述了 面条老师 的 QQ 个问题。每行包含两个整数,kik_iviv_i1ki1091 \leq k_i \leq 10^91viN1 \leq v_i \leq N),表示 面条老师 的第 ii 个问题询问中当 K=kiK = k_i 时,第 viv_i 个视频推荐列表中将推荐的视频数。

输出格式

输出 QQ 行。在第 ii 行,输出 面条老师 的第 ii 个问题的答案。

样例 #1

样例输入 #1

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

样例输出 #1

3
0
2