Woburn Challenge 2018-19 Finals Round - Senior Division

Problem 5: Opening Weekend

At last, the time has come for months of hard work to finally pay off — the cows' and monkeys' production is hitting the big screen this weekend!

It will be playing at movie theatres in N (2 ≤ N ≤ 400,000) different cities, numbered from 1 to N in increasing order of their theatres' quality. There are N − 1 roads running amongst these cities, the i-th of which allows vehicles to drive in either direction between cities Ai and Bi (1 ≤ Ai, BiN, AiBi). However, each road also passes through a tunnel which imposes a limit on the heights of vehicles which may drive along it — in particular, a vehicle may only travel along the i-th road if its height is at most Li cm (1 ≤ Li ≤ 109). It's possible for a 1cm-high vehicle (if such a thing exists) to travel from any city to any other city by following a sequence of roads.

There are K (1 ≤ K ≤ 400,000) moviegoers who have been waiting anxiously to see the film, with the i-th one living in city Ci (1 ≤ CiN) and driving a vehicle with a height of Hi cm (1 ≤ Hi ≤ 109). However, they won't necessarily settle for watching the film in their own cities — they're prepared to drive wherever it takes to get the best possible movie-watching experience! However, they're also not great at planning ahead, so each moviegoer will follow this simple procedure:

  1. They'll consider both their current city and all cities they can directly reach from that city (by driving along a single road whose tunnel their vehicle can fit through), and find the one with the highest-quality movie theatre (the largest city number).
  2. If that largest-numbered city is their current city, they'll stop to watch the film there.
  3. Otherwise, they'll drive to that largest-numbered city, and repeat the procedure from Step 1.

The Head Monkey and Bo Vine want to make sure that each theatre has enough seats available for its screening — nobody should be left out from witnessing their masterpiece! In order to help estimate audience sizes, determine which city each of the K moviegoers will end up stopping at to watch the film.


In test cases worth 5/34 of the points, N ≤ 2000 and K ≤ 2000.
In test cases worth another 12/34 of the points, each city has at most two roads directly adjacent to it.

Input Format

The first line of input consists of two space-separated integers, N and K.
N − 1 lines follow, the i-th of which consists of three space-separated integers, Ai, Bi, and Li, for i = 1..(N − 1).
K lines follow, the i-th of which consists of two space-separated integers, Ci and Hi, for i = 1..K.

Output Format

Output K lines, the i-th of which should consist of a single integer, the city at which moviegoer i will stop to watch the film, for i = 1..K

Sample Input

3 3
1 2 10
3 1 5
1 4
2 1
1 10

Sample Output


Sample Explanation

The first moviegoer will drive from city 1 to city 3 and then remain there.
The second moviegoer will remain at city 2.
The third moviegoer will drive from city 1 to city 2 and then remain there.

All Submissions
Best Solutions

Point Value: 25 (partial)
Time Limit: 8.00s
Memory Limit: 256M
Added: May 18, 2019
Author: SourSpinach

Languages Allowed:

Comments (Search)

It's quiet in here...