RTE '16 S3 - School Traversal

View as PDF

Submit solution

Points:7 (partial)
Time limit:4.0s
Memory limit:256M

Problem type

Ellen is a student at RHHS who is trying to navigate her way through the school to get to her classes. She knows that most halls are going to be blocked off by large groups of aimless students, so she has devised a map of the school which only includes hallways she knows will be open. In particular, the school can be represented as a collection of N classrooms numbered 0 to N - 1 with N - 1 hallways between them. It is guaranteed that these hallways will never form a loop.

Because Ellen is travelling around the school a lot, she wants to know how far it is between various different locations in the school, so she can plan how long it will take to walk between them.

To help her with this, you will be given Q queries; for each one you must determine the distance between the two given classrooms.

Input Specification

The first line will contain N (3 \leq N \leq 6\,000), the number of classrooms.

The next N - 1 lines will contain three space-separated integers, a_i, b_i, w_i, (0 \leq a_i,b_i \leq N - 1, 1 \leq w_i \leq 500\,000), indicating that there is a hallway between classrooms a_i and b_i with length w_i.

The next line will contain Q (1 \leq Q \leq 1\,000\,000), the number of queries to be answered.

The next Q lines will contain two space-separated integers, u_i and v_i (0 \leq u_i, v_i \leq N - 1), representing a query that asks the distance between classrooms u_i and v_i.

For test cases worth 20 of 100 points, 3 \leq N \leq 500 and 1 \leq Q \leq 10\,000.

For test cases worth an additional 20 points, 3 \leq N \leq 500.

Output Specification

For each query, output a single integer on its own line which is the distance between the two classrooms in the query.

Sample Input

0 1 3
0 3 2
0 4 7
1 2 5
2 0
1 4
3 1
3 4

Sample Output



  • -13
     commented on June 8, 2017

    Because \mathcal O(N^2) preprocessing passes, the problem has been lowered to 7 points.

    • 1
       commented on June 10, 2017

      was that not an intended solution?

      or did they just not want data to be huge?

      • 1
         commented on June 10, 2017

        Likely the latter, as their solution was \mathcal O(N + Q)

    • 3
       commented on June 8, 2017

      Seriously? I was halfway through solving this problem when you lowered the points. If anything, just tighten the time limit if you think it is too easy.

      • 3
         commented on June 10, 2017

        That's up to the problemsetter as the admins would be encroaching on their "creative license" by changing the time limit.