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 A_i and B_i (1 ≤ A_i, B_i ≤ N, A_i ≠ B_i). 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 L_i cm (1 ≤ L_i ≤ 10⁹). 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 C_i (1 ≤ C_i ≤ N) and driving a vehicle with a height of H_i cm (1 ≤ H_i ≤ 10⁹). 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.

Subtasks

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, A_i, B_i, and L_i, for i = 1..(N − 1).
K lines follow, the i-th of which consists of two space-separated integers, C_i and H_i, 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

3
2
2

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:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)