题目描述(ID:12351)
标题: Ahatube(MooTube)
标签: 数据结构 并查集
详情:
啊哈沃德正在大力发展动漫周边,他架设了一家经营动漫直播的网站,取名为AhaTube。经过一段时间发展,网站上已经有了N个动漫资源(1<=N<=5000)。啊哈沃德发现当动漫资源太多的时候,搜索会变得麻烦。因此他决定开发一个“相似内容推荐”的功能。

首先,他根据现有的N个动漫内容,给相似的动漫两两之间设定了它们相似度。然后,他开始设置推荐的规则,当某个动漫被观看时,与它(和它的相似动漫)相似度大于等于K的动漫都会被推荐给观看者。

现在,已知N部动漫间的相似关系,求在设置不同K值的情况下,观看某一部动漫时,被推荐的其他动漫数量是多少?
输入格式:
第一行有两个整数N,Q(1<=N,Q<=5000)
接下来N-1行有 N-1对关系,每行包括三个整数pi, qi和ri,(1<=pi,qi<=N, 1<=ri<=1000000000),表明动漫pi和qi之间的相似度为ri。
接下来Q行有Q个问题,每行包括两个整数ki和vi,(1<=ki<=1000000000, 1<=vi<=N),问当设置K=ki时,观看动漫vi时,有多少部动漫会被同时推荐给观看者
输出格式:
输出包括Q行,每行对应输入中的一问,即当设置K=ki时,观看动漫vi时,有多少部动漫会被同时推荐给观看者。
提示: 本题改编自USACO 2018 Mootube
样例:

输入

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之间最小的相关度为2,1与4之间的最小相关度为3,3与4之间的最小相关度为2.
然后开始回答问题,对于动漫2,当K=1时,1,3,4都会被推荐,故答案为3
对于动漫1,当K=4时,没有动漫会被推荐,故答案为0
对于动漫1,当K=3时,2,4会被推荐,故答案为2
登录并解答