WC '18 Finals S5 - Opening Weekend

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 3.5s
Memory limit: 256M

Author:
Problem type
Woburn Challenge 2018-19 Finals Round - Senior Division

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 \le N \le 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 \le A_i, B_i \le N, A_i \ne 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 \le L_i \le 10^9). It's possible for a 1 cm-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 \le K \le 400\,000) moviegoers who have been waiting anxiously to see the film, with the i-th one living in city C_i (1 \le C_i \le N) and driving a vehicle with a height of H_i cm (1 \le H_i \le 10^9). 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 \le 2\,000 and K \le 2\,000.
In test cases worth another 12/34 of the points, each city has at most two roads directly adjacent to it.

Input Specification

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

Output Specification

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 \dots 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.


Comments

There are no comments at the moment.