RiseOJ – MooTube

설명

농부 존은 여가 시간에 MooTube라는 이름의 새로운 동영상 공유 서비스를 만들었다. MooTube에서 농부 존의 소들은 재미있는 동영상을 녹화하고, 공유하고, 발견할 수 있다. 소들은 이미 $$N$$ 개의 동영상 ( $1 \leq N \leq 100,000$ )을 올렸으며, 편의상 $1 \ldots N$ 으로 번호가 매겨져 있다. 하지만 농부 존은 소들이 좋아할 만한 새 동영상을 찾도록 도와줄 방법을 좀처럼 알아내지 못하고 있다.

농부 존은 모든 MooTube 동영상에 대해 "추천 동영상" 목록을 만들고 싶다. 이렇게 하면 소들은 자신이 이미 시청한 동영상과 가장 관련이 높은 동영상들을 추천받게 된다.

농부 존은 "관련도"라는 지표를 고안했는데, 이름 그대로 두 동영상이 서로 얼마나 관련이 있는지를 나타낸다. 그는 $$N-1$$ 쌍의 동영상을 골라 각 쌍의 관련도를 직접 계산한다. 그런 다음, 농부 존은 동영상들을 네트워크로 시각화하는데, 각 동영상이 노드가 되고 그가 직접 고려한 $$N-1$$ 쌍의 동영상들이 연결된다. 편리하게도, 농부 존은 어떤 동영상에서든 다른 어떤 동영상으로든 연결들을 따라가는 경로가 정확히 하나만 존재하도록 $$N-1$$ 개의 쌍을 골랐다. 농부 존은 임의의 두 동영상 사이의 관련도를 이 경로 위의 연결들 중 최소 관련도로 정의하기로 했다.

농부 존은 어떤 값 $$K$$ 를 골라서, 임의의 MooTube 동영상 옆에 그 동영상과의 관련도가 $$K$$ 이상인 다른 모든 동영상이 추천되도록 하고 싶다. 하지만 농부 존은 너무 많은 동영상이 추천되면 소들이 우유 생산에 집중하지 못할까 봐 걱정이다! 따라서 그는 적절한 $$K$$ 값을 신중하게 정하고 싶다. 농부 존은 특정 $$K$$ 값들에 대한 추천 동영상에 관한 여러 질문에 답하는 데 여러분의 도움을 받고 싶어한다.

Problem credits: Jay Leeds

제약

Problem credits: Jay Leeds

입력 형식

입력의 첫째 줄에 $$N$$ 과 $$Q$$ ( $1 \leq Q \leq 100,000$ )가 주어진다.

다음 $$N-1$$ 개의 줄에 농부 존이 직접 비교한 동영상 쌍이 하나씩 주어진다. 각 줄은 세 정수 $$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$$ 개의 줄에 농부 존의 질문 $$Q$$ 개가 주어진다. 각 줄은 두 정수 $$k_i$$ 와 $$v_i$$ ( $1 \leq k_i \leq 1,000,000,000, 1 \leq v_i \leq N$ )로 이루어져 있으며, 농부 존의 $$i$$ 번째 질문은 $$K = k_i$$ 일 때 동영상 $$v_i$$ 의 시청자에게 몇 개의 동영상이 추천되는지를 묻는다는 의미이다.

출력 형식

$$Q$$ 개의 줄을 출력한다. $$i$$ 번째 줄에 농부 존의 $$i$$ 번째 질문에 대한 답을 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 mootube.in · 출력을 쓸 파일 mootube.out

예제 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.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2017-2018 > January > Gold

올림피아드 > USACO > 2017-2018 > January > Gold

태그

JudgeUSACO

MooTube

평가 및 의견

풀이 제출