P4185 [USACO18JAN] MooTube G

This problem has the same statement as the [Silver version](/problem/P6111); 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 10^5$), conveniently numbered $1 \ldots N$. 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. This way, cows will be recommended videos that are most related to the videos they have already watched. FJ designed a “relevance” metric that, as the name suggests, measures how related two videos are. FJ models his videos as a tree (where each node represents a video) and computes the relevance for all $N-1$ pairs of adjacent videos. In this way, any video can reach any other video via a connected path. FJ defines the relevance of any pair of videos as the minimum relevance along the edges on the path between them. Farmer John wants to choose a value $K$ so that, next to any given MooTube video, he will recommend all other videos whose relevance to that video is at least $K$. However, FJ worries about recommending too many videos, which might distract the cows from producing milk. Therefore, he wants to set an appropriate value of $K$. Farmer John needs your help to answer some questions about the recommended videos for given $K$ values.

The first line contains $N$ and $Q$ ($1 \leq Q \leq 10^5$). Each of the next $N-1$ lines describes a pair 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 and have relevance $r_i$. Each of the next $Q$ lines describes one of 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 FJ’s $i$-th query, when $K = k_i$, you should report how many videos would be recommended in the 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