P4185 [USACO18JAN]MooTube

    • 242通过
    • 424提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 并查集 概率论,统计 连通块 USACO 2018
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    在业余时间,Farmer John创建了一个新的视频共享服务,他将其命名为MooTube。在MooTube上,Farmer John的奶牛可以录制,分享和发现许多有趣的视频。他的奶牛已经发布了 $N$ 个视频 ( $1 \leq N \leq 100,000$ ),为了方便将其编号为 $1 \ldots N$ 。然而,FJ无法弄清楚如何帮助他的奶牛找到他们可能喜欢的新视频。

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

    FJ设计了一个“相关性”度量标准,顾名思义,它确定了两个视频相互之间的相关性。他选择 $N-1$ 对视频并手动计算其之间的相关性。然后,FJ将他的视频建成一棵树,其中每个视频是节点,并且他手动将 $N-1$ 对视频连接。为了方便,FJ选择了 $N-1$ 对,这样任意视频都可以通过一条连通路径到达任意其他视频。 FJ决定将任意一对视频的相关性定义为沿此路径的任何连接的最小相关性。

    Farmer John想要选择一个 $K$ 值,以便在任何给定的MooTube视频旁边,推荐所有其他与该视频至少有 $K$ 相关的视频。然而,FJ担心会向他的奶牛推荐太多的视频,这可能会分散他们对产奶的注意力!因此,他想设定适当的 $K$ 值。 Farmer 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$ 行描述了Farmer 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$ 个问题的答案。

    感谢@MxI_box 提供的翻译

    题目描述

    In his spare time, Farmer John has created a new video-sharing service, which he names MooTube. On MooTube, Farmer John's cows can record, share, and discover many amusing videos. His cows already have posted $N$ videos ($1 \leq N \leq 100,000$), conveniently numbered $1 \ldots N$. However, FJ can't quite figure out how to help his cows find new videos they might like.

    FJ wants to create a list of "suggested videos" for every MooTube video. This way, cows will be recommended the videos most relevant to the ones they already watch.

    FJ devises a metric of "relevance," which determines, as the name suggests, how relevant two videos are to each other. He picks $N-1$ pairs of videos and manually computes their pairwise relevance. Then, FJ visualizes his videos as a network, where each video is a node and the $N-1$ pairs of videos he manually considered are connected. Conveniently, FJ has picked his $N-1$ pairs so that any video can be reached from any other video along a path of connections in exactly one way. FJ decides that the relevance of any pair of videos should be defined as the minimum relevance of any connection along this path.

    Farmer John wants to pick a value $K$ so that next to any given MooTube video, all other videos with relevance at least $K$ to that video will be suggested. However, FJ is worried that too many videos will be suggested to his cows, which could distract them from milk production! Therefore, he wants to carefully set an appropriate value of $K$. Farmer John would like your help answering a number of questions about the suggested videos for certain values of $K$.

    输入输出格式

    输入格式:

    The first line of input contains $N$ and $Q$ ($1 \leq Q \leq 100,000$).

    The next $N-1$ lines each describe a pair of videos FJ manually compares. Each line includes three integers $p_i$, $q_i$, and $r_i$ ($1 \leq p_i, q_i \leq N, 1 \leq r_i \leq 1,000,000,000$), indicating that videos $p_i$ and $q_i$ are connected with relevance $r_i$.

    The next $Q$ lines describe Farmer John's $Q$ questions. Each line contains two integers, $k_i$ and $v_i$ ($1 \leq k_i \leq 1,000,000,000, 1 \leq v_i \leq N$), indicating that FJ's $i$th question asks how many videos will be suggested to viewers of video $v_i$ if $K = k_i$.

    输出格式:

    Output $Q$ lines. On line $i$, output the answer to FJ's $i$th question.

    输入输出样例

    输入样例#1: 复制
    4 3
    1 2 3
    2 3 2
    2 4 4
    1 2
    4 1
    3 1
    输出样例#1: 复制
    3
    0
    2
    

    说明

    Farmer John finds that videos one and two have relevance three, that videos two and three have relevance two, and that videos two and four have relevance four. Based on this, videos one and three have relevance min(3, 2) = 2, videos one and four have relevance min(3, 4) = 3, and videos three and four have relevance min(2, 4) = 2.

    Farmer John wants to know how many videos will be suggested from video two if $K=1$, from video one if $K=3$, and from video one if $K=4$. We see that with $K=1$, videos 1, 3, and 4 will be suggested on video two. With $K=4$, no videos will be suggested from video one. With $K=3$, however, videos 2 and 4 will be suggested from video one.

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。