RTE '16 S3 - School Traversal

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.8s
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 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 \le N \le 6\,000), the number of classrooms.

The next N-1 lines will contain three space-separated integers, a_i, b_i, w_i (0 \le a_i,b_i \le N-1, 1 \le w_i \le 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 \le Q \le 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 \le u_i, v_i \le 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 \le N \le 500 and 1 \le Q \le 10\,000.

For test cases worth an additional 20 points, 3 \le N \le 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



  • 4
    Roronoa_Zoro1540  commented on Jan. 29, 2018, 12:02 a.m.

    are hallways bidirectional?

  • -64
    Kirito  commented on June 8, 2017, 5:15 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.

    • 3
      imaxblue  commented on June 11, 2017, 1:19 a.m.

      was that not an intended solution?

      or did they just not want data to be huge?

      • -11
        Kirito  commented on June 11, 2017, 1:27 a.m.

        This comment is hidden due to too much negative feedback. Show it anyway.

    • 8
      root  commented on June 9, 2017, 12:33 a.m.

      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.

      • -5
        P234rex  commented on June 11, 2017, 3:03 a.m.

        This comment is hidden due to too much negative feedback. Show it anyway.