All Tracks>Problem
Expected path distance
★★★★★

4

4 votes
Dynamic Programming, Algorithms, Trees, LCA
Problem

Your country consists of n cities. Each city contains exactly one simple path. You are required to solve q queries if you want to visit the cities of your country.

In each query, you are required to select two cities A and B where city A is your current location. You must stop when you reach your destination. Your task is to determine that if each city that is situated on the simple path between A and B  can be selected as the destination (both included), what is the expected value of the distance that is covered by you when you starts from city A.

As the expected value can be represented as PQ where P and Q are co-prime to each other. You are required to determine PQ−1mod(109+7).

Note: The distance referred here is the shortest distance between the two cities.

Input format

  • First line: n denoting the number of cities in the country

  • Next n−1 lines: u,v, and w three space-separated integers that denote city u and city v are directly connected to each other at a distance w

  • Next line: q denoting the number of queries

  • Next q lines: A and B denoting two space-separated as described in the problem statement

Output format

Print q lines containing a single integer that denotes the required answer.

Constraints

1≤n,q≤3⋅105

1≤u,v,A,B≤n

1≤w≤108

Sample Input
10
1 2 2
3 1 6
4 3 1
3 5 2
4 6 6
4 7 2
5 8 3
5 9 4
9 10 5
6
10 6
6 10 
8 2
1 7
2 2
3 8
Sample Output
166666677
833333348
800000012
500000009
0
333333338
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

tree_example

For the first query:
The cities are A = 10 and B = 6 as there are 6 cities between A and B, the probability of choosing any city is 1/6. So the required expected value is 1/6 x (summation of total distance between cities (10, 10), (10, 9), (10, 5), (10, 3), (10, 4) and (10, 6). i.e. 1/6 x (0 + 5 + 9 + 11 + 12 + 18) = 1/6 x 55 = 55 / 6. answer = 55 x 6^-1 mod (1e9 + 7) = 166666677.

For the second query:
The cities are A = 8 and B = 2 as there are 5 cities between A and B, the probability of choosing any city is 1/5. So the required expected value is 1/5 x (summation of total distance between cities (8, 8), (8, 5), (8, 3), (8, 1) and (8, 2). i.e. 1/5 x (0 + 3 + 5 + 11 + 13) = 1/5 x 32 = 32 / 5. answer = 32 x 5^-1 mod (1e9 + 7) = 800000012.
Similarly for remaining queries.

Contributers:
Editor Image

?