Expected path distance
Practice
4 (4 votes)
Dynamic programming
Algorithms
Trees
Lca
Problem
92% Success 168 Attempts 30 Points 2s Time Limit 256MB Memory 1024 KB Max Code

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 \(P \over Q\) where \(P\) and \(Q\) are co-prime to each other. You are required to determine \(PQ^{-1} \bmod (10 ^ 9 + 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 \leq n, q \leq 3 \cdot10 ^ 5\)

\(1 \leq u, v, A, B \leq n\)

\(1 \leq w \leq 10 ^ 8\)

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
1 votes
Tags:
Dynamic ProgrammingTreeMediumAlgorithmsKadaneDepth-first search
Points:30
8 votes
Tags:
Binary search algorithmDynamic ProgrammingAlgorithmsMediumTree
Points:30
12 votes
Tags:
AlgorithmsDepth-first searchTreesDynamic Programming