Base Simplification

This problem is adapted from the 2023 International Olympiad in Informatics Representative Student Selection Contest.

In the distant future, humanity has spread to many extraterrestrial planets. On planet X, the exploration company MR has established N bases connected by N-1 bidirectional channels such that every two different bases are connected (i.e. the bases and channels form a tree). The bases are numbered from 0 to N-1. For each i (0 ≤ i ≤ N-2), the i-th channel connects base U[i] and base V[i] and has a length of W[i] kilometers.

As the development of planet X becomes stable, the maintenance cost of all bases and channels becomes very high. Therefore, MR decides to keep only a subset of the bases while deactivating the others. Suppose that only the bases numbered from s to e (0 ≤ s ≤ e ≤ N-1) are kept. The maintenance cost in this case is defined as follows:

• Choose 0 or more channels such that the following condition is satisfied and the total length of the chosen channels is minimized (if 0 channels are chosen, the total length is 0 kilometers).
• For any u, v with s ≤ u < v ≤ e, base u and base v can reach each other via the chosen channels. (It is allowed to pass through deactivated bases.)
• If the chosen channels have a total length of C kilometers, then the maintenance cost is C.

MR is interested in knowing, for all possible combinations (i, j) with 0 ≤ i ≤ j ≤ N-1, the sum of maintenance costs when only bases numbered from i to j are kept. Since the result can be very large, output it modulo \(10^9+7\).

Note: In a tree the minimal set of channels needed to connect a set S of bases is the union of the unique simple paths between any two bases in S. An edge will be used if and only if the chosen interval [s,e] (in terms of base numbers) has at least one base in each of the two connected components obtained by removing that edge. In other words, if removal of an edge splits the tree into two sets A and B, the edge contributes its weight to the cost for those intervals [s,e] which intersect both A and B. Counting these intervals carefully (by subtracting intervals completely inside A or B) is the key observation to solving the problem.

inputFormat

The function maintenance_costs_sum is given three arrays:

• U: an array of integers of length N-1, representing one endpoint of each channel.
• V: an array of integers of length N-1, representing the other endpoint of each channel.
• W: an array of integers of length N-1, where W[i] represents the length (in kilometers) of the channel connecting U[i] and V[i].

It is guaranteed that the bases (0 to N-1) together with these channels form a tree.

The number of bases N is equal to len(U) + 1.

outputFormat

The function should return a single integer which is the sum of maintenance costs for all contiguous intervals of bases \([i,j]\) (with 0 ≤ i ≤ j ≤ N-1), modulo \(10^9+7\).

sample

U = []
V = []
W = []

0