P6111 [USACO18JAN] MooTube S

*This problem has the same statement as [the Gold problem with the same name](/problem/P4185); the only difference is the constraints.*

In his spare time, Farmer John created a new video-sharing service, which he named MooTube. On MooTube, Farmer John’s cows can record, share, and discover many interesting videos. His cows have posted $N$ videos ($1 \leq N \leq 5000$), numbered $1 \ldots N$ for convenience. However, FJ cannot figure out how to help his cows find new videos they might like. FJ wants to create a “recommended videos” list for each MooTube video. In this way, cows will be recommended videos that are most related to the videos they have already watched. FJ designed a “relevance” measure, as the name suggests, to determine how related two videos are. He chose $N - 1$ pairs of videos and manually computed the relevance between each pair. Then, FJ built his videos into a tree, where each video is a node, and he manually connected the $N - 1$ pairs of videos. For convenience, FJ chose these $N - 1$ pairs so that any video can reach any other video via a connected path. FJ decides to define the relevance between any two videos as the minimum relevance of any edge along this path. Farmer John wants to choose a value $K$ so that, next to any given MooTube video, all other videos with relevance at least $K$ to that video will be recommended. However, FJ worries that he might recommend too many videos to his cows, which could distract them from producing milk. Therefore, he wants to set an appropriate value of $K$. Farmer John would like your help in answering some queries about the recommended videos for different values of $K$.

The first line contains $N$ and $Q$ ($1 \leq Q \leq 5000$). The next $N - 1$ lines describe the pairs of videos that FJ compared manually. Each line contains three integers $p_i$, $q_i$, and $r_i$ ($1 \leq p_i, q_i \leq N$, $1 \leq r_i \leq 10^9$), indicating that videos $p_i$ and $q_i$ are connected with relevance $r_i$. The next $Q$ lines describe Farmer John’s $Q$ queries. Each line contains two integers $k_i$ and $v_i$ ($1 \leq k_i \leq 10^9$, $1 \leq v_i \leq N$), meaning that in the $i$-th query, FJ asks: when $K = k_i$, how many videos will appear in the recommended list for video $v_i$.

Output $Q$ lines. On the $i$-th line, output the answer to FJ’s $i$-th query.

Translated by ChatGPT 5