Under construction

Still being built. Things may change

Distance Between Vertices

Time limit2sMemory limit128 MB

Summary
Given a weighted tree with up to 40,000 nodes, answer up to 10,000 queries about the path distance between two vertices, requiring an LCA-based approach for efficiency.
Level

Medium5 of 10

Topics
Tree, Binary search, DFS, Math
Solved
No attempts yet

Problem

You are given a weighted tree with N vertices. Then M pairs of vertices are given. For each pair, output the length of the path between the two vertices.

  • 2 <= N <= 40,000
  • 1 <= M <= 10,000

Input

The first line contains the number of vertices N. Each of the next N - 1 lines contains two vertices connected by an edge and the distance of that edge.

The next line contains the number of queries M. Each of the next M lines contains one pair of vertices whose distance should be found.

Vertices are numbered from 1 to N. Each edge distance is a positive integer no greater than 10,000.

Output

For each of the M queries, output the distance between the given two vertices on its own line, in input order.

Examples1

  1. Example 1

    Input
    7
1 6 13
6 3 9
3 5 7
4 1 3
2 4 20
4 7 2
3
1 6
1 4
2 6
    Expected output
    13
3
36