WOSS Dual Olympiad 2023 S3: Flying

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 5.0s
Memory limit: 1G

Problem type

Manasva "JARVIS" Katyal is going on an adventure in his beloved Grob 120A. There are N destinations connected by N-1 routes. The ith route connects destination u_i with destination v_i, using up l_i units of fuel. Routes can be flown both ways and multiple times. It is possible to reach every destination from every other destination using these routes. Since Manasva spent his life savings buying the Grob 120A, he's being really frugal and wants to save fuel. He asks Q questions. For each question, he asks if it would be possible to fly from destination 1 to q_i while using exactly c_i units of fuel.


1 \leq N \leq 10^3

1 \leq Q \leq 10^6

1 \leq u_i, v_i, q_i \leq N

1 \leq l_i \leq 10^3

Subtask 1 [40%]

1 \leq c_i \leq 10^3

Subtask 2 [60%]

1 \leq c_i \leq 10^9

Input Specification

The first line contains 2 space-separated integers, N and Q.

The next N-1 lines each contain 3 space-separated integers, u_i, v_i, and l_i, indicating a route connecting destination u_i with destination v_i which uses l_i units of fuel.

The next Q lines each contain 2 space-separated integers, q_i and c_i.

Output Specification

For each query, output a single line containing YES if there exists a path and NO if there is no valid path.

Sample Input

5 4
2 1 9
1 4 4
2 5 11
3 1 6
3 24
1 17
3 21
2 47

Sample Output



There are no comments at the moment.