파일 업로드

추천 동영상

profile
실행 시간 제한메모리 제한
2 초512 MB
📃 해결할 문제

휴가 동안, 개발자 주환은 JTube라는 새로운 동영상 공유 서비스를 만들었습니다. JTube에서 친구들은 재미있는 동영상을 녹화하고, 서로 공유하며, 발견할 수 있습니다. 이미 친구들은 NN개의 동영상 (1N50001 \leq N \leq 5000)을 게시했고, 이를 편리하게 1N1 \ldots N으로 번호가 매겨졌습니다. 그러나 주환은 친구들이 좋아할 만한 새로운 동영상을 어떻게 찾아주어야 할 지 알아내지 못하고 있습니다.

주환은 모든 JTube 동영상에 대해 '추천 동영상' 목록을 만들고 싶어합니다. 이렇게 하면 친구에게 이미 보고 있던 동영상과 가장 관련이 있는 동영상들을 추천할 수 있게 됩니다.

주환은 '관련성'이라는 척도를 고안하였는데, 이는 두 동영상이 서로 얼마나 관련성이 있는 지를 판단합니다. 그는 N1N-1개의 동영상 쌍을 선택하고 그들 사이의 관련성을 수동으로 계산합니다. 그 다음, 주환은 각 동영상이 노드이고 그가 수동으로 고려하였던 N1N-1개의 동영상 쌍이 연결되어 있는 네트워크로 동영상을 시각화합니다. 편리하게도, 주환은 임의의 동영상이 정확히 하나의 연결 경로를 따라 다른 동영상에 도달할 수 있도록 N1N-1개의 쌍을 선택했습니다. 주환은 두 동영상 간의 관련성은 이 경로상의 모든 연결의 최소 관련성으로 정의되어야 한다고 결정합니다.

주환은 주어진 JTube 동영상 옆에, 그 비디오와의 관련성이 KK 이상인 모든 다른 동영상들이 추천되도록 KK 값을 설정하려고 합니다. 그러나, 주환은 너무 많은 동영상들이 친구들에게 추천될 수 있을 것을 걱정하고 있는데, 이는 그들의 시험 공부를 방해할 수 있습니다! 따라서 그는 신중하게 KK 값의 적합한 수준을 설정하려고 합니다. 주환은 KK 값에 따른 추천 동영상에 대한 여러 가지 질문에 대한 답변하는 것을 당신이 도와주는 것을 원합니다.

💻 입력

첫 번째 입력 줄에는 NNQQ (1Q50001 \leq Q \leq 5000)가 포함됩니다.

다음 N1N-1개의 줄은 주환이 수동으로 비교한 동영상 쌍을 각각 설명합니다. 각 줄에는 세 개의 정수 pip_i, qiq_i, 그리고 rir_i (1pi,qiN,1ri1,000,000,0001 \leq p_i, q_i \leq N, 1 \leq r_i \leq 1,000,000,000)가 포함되어 있으며, 이는 pip_iqiq_i 동영상이 rir_i의 관련성으로 연결되어 있음을 나타냅니다.

다음 QQ개의 줄은 주환의 QQ개의 질문을 설명합니다. 각 줄에는 두 개의 정수, kik_iviv_i (1ki1,000,000,000,1viN1 \leq k_i \leq 1,000,000,000, 1 \leq v_i \leq N)가 포함되어 있으며, 이는 FJ의 ii번째 질문이 K=kiK = k_i일 때 비디오 viv_i를 보는 사람들에게 몇 개의 동영상이 추천될 것인지 묻는다는 것을 의미합니다.

🖨️ 출력

QQ개의 줄을 출력합니다. ii번째 줄에는 FJ의 ii번째 질문에 대한 답변을 출력합니다.


💻 예제 입력 1
4 3
1 2 3
2 3 2
2 4 4
1 2
4 1
3 1
🖨️ 예제 출력 1
3
0
2

💡 힌트

주환은 동영상 1과 2가 관련성이 3인 것을, 동영상 2와 3이 관련성이 2인 것을, 그리고 동영상 2와 4가 관련성이 4인 것을 발견합니다. 이를 기반으로, 동영상 1과 3의 관련성은 min(3, 2) = 2이며, 동영상 1과 4의 관련성은 min(3, 4) = 3이며, 그리고 동영상 3과 4의 관련성은 min(2, 4) = 2입니다.

주환은 K=1K=1일 때 동영상 2에서 몇 개의 동영상이 추천될지, K=3K=3일 때 동영상 1에서 몇 개의 동영상이 추천될지, 그리고 K=4K=4일 때 동영상 1에서 몇 개의 동영상이 추천될지 알고 싶어합니다. 우리는 K=1K=1일 때, 동영상 1, 3, 그리고 4가 동영상 2에서 추천되는 것을 볼 수 있습니다. K=4K=4일 때는 동영상 1에서 어떤 동영상도 추천되지 않을 것입니다. 그러나 K=3K=3일 때는 동영상 2와 4가 동영상 1에서 추천될 것입니다.


출처: USACO 2018 January Contest, Silver Problem 3. MooTube