MooTube (Silver)#10422
In his spare time, Farmer John created his own video-sharing platform called MooTube. On MooTube, his cows can record, publish, and discover lots of funny videos. So far, the cows have uploaded videos, numbered from to .
However, Farmer John doesn't fully understand how to help his cows find new videos they might enjoy. He wants to implement a recommendation system for each video — a list of "recommended videos" based on their similarity to videos already watched.
To determine how similar two videos are, John introduces a relevance metric. He manually evaluates n - 1 pairs of videos and assigns each pair a relevance score. Using these pairs, John builds a network where each video is a node in a graph, and the selected pairs are connected by edges with the given relevance values.
For convenience, John selects the n - 1 pairs in such a way that there is exactly one path between any two videos — in other words, the video network forms a tree.
He decides that the relevance between two videos should be defined as the minimum relevance among all edges along the path connecting them.
Now, Farmer John wants to choose a value such that, for any video on MooTube, all other videos with relevance at least to it will be displayed as recommendations. However, he worries that too many recommendations might distract his cows from producing milk, so he wants to precisely estimate how many videos would be recommended for various values of .
Farmer John turns to you for help: you are given several queries, each consisting of a value and a video number. For each query, you need to determine how many other videos would be recommended if the minimum required relevance is .
The first line contains two integers and q~(1 \le n, q \le 5000) — the number of videos and the number of queries, respectively.
The next n − 1 lines describe pairs of videos whose relevance has been manually evaluated by Farmer John. Each of these lines contains three integers p_i, q_i and r_i~(1 \le p_i, q_i \le n, 1 \le r_i \le 10^9), meaning that videos p_i and q_i are connected by an edge with relevance r_i.
Then follow lines, each describing one of Farmer John's queries. The -th line contains two integers k_i and v_i~(1 \le k_i \le 10^9, 1 \le v_i \le n) — meaning that in the -th query, Farmer John wants to know how many videos will be recommended for video v_i if the minimum acceptable relevance for recommendations is k = k_i.
Print lines. In the -th line, output the answer to Farmer John's -th query.
Farmer John has established the following connections between videos:
Video and video have a relevance of ,
Video and video have a relevance of ,
Video and video have a relevance of .
Based on this data, we can compute the relevance between other pairs of videos:
Video and video : relevance = min(3, 2) = 2,
Video and video : relevance = min(3, 4) = 3,
Video and video : relevance = min(2, 4) = 2.
Now let's see which videos will be recommended for the following queries:
From video with k = 1, videos , and will be recommended.
From video with k = 3, videos and will be recommended.
From video with k = 4, no videos will be recommended.
Example 1