# KOITST 23 Base Streamlining

https://www.acmicpc.net/problem/27605

In the distant future, humanity has expanded to numerous alien planets. Planet X is one of them, and the space exploration company MR has built bases on Planet X to conduct exploration and resource extraction activities.

Planet X has $N$ bases and $N-1$ bidirectional pathways connecting the bases, allowing travel between any two distinct bases only via pathways. In other words, the bases and pathways on Planet X form a tree structure.

Each base is numbered with a different number from $0$ to $N - 1$. Additionally, for all $0\leq i \leq N-2$, road $i$ connects cities $U[i]$ and $V[i]$ with a pathway length of $W[i]$ km.

As development on Planet X approaches stability, it becomes costly to maintain all bases and pathways. Therefore, MR has decided to keep only some bases active and deactivate the rest.

For any $(s, e)$ ($0 \leq s \leq e \leq N - 1$), let's say only bases $s, s+1, \dots, e$ are kept active. The maintenance cost is defined as follows:

* Choose zero or more pathways such that the following condition is satisfied. Choose the pathways in a way that minimizes the sum of their lengths. (If no pathways are chosen, the sum of lengths is $0$ km.)
* For any $u, v$ ($s \leq u < v \leq e$), it should be possible to travel between base $u$ and base $v$ using only the chosen pathways. It's allowed to pass through deactivated bases during the journey.

The maintenance cost is $C$ when the sum of lengths of the chosen pathways is $C$ km.

## Implementaiton

You need to implement the following function:

This function is called only once.
* $U$, $V$, $W$: Integer arrays of size $N-1$. For all $i$ ($0 \leq i \leq N - 2$), there is a pathway of length $W[i]$ km connecting base $U[i]$ and base $V[i]$.
* This function should return the sum of maintenance costs for keeping only bases $i, i+1, \dots, j$ active for all possible pairs $(i, j)$ ($0 \leq i \leq j \leq N - 1$), modulo $1,000,000,007$.

No input/output functions should be executed in any part of the submitted source code.

## Constraints

* $2 \leq N \leq 250,000$
* For all $i$, $0 \leq U[i], V[i] \leq N-1$; $U[i] \neq V[i]$ ($0 \leq i \leq N - 2$)
* For all $i$, $1 \leq W[i] \leq 10^9$ ($0 \leq i \leq N - 2$)

## Subtasks

1. 5 points: $N \leq 300$
1. 6 points: $N \leq 4,000$
1. 10 points: The numbering of bases follows one of the preorder traversal orders of the tree with base $0$ as the root.
1. 26 points: Each base is connected to at most 2 pathways.
1. 53 points: No additional constraints.

## Samples

### Example 1

Let's consider the case where $N = 5$, $U = [0, 2, 2, 0]$, $V = [2, 1, 4, 3]$, $W = [2, 3, 6, 5]$.

The grader calls the following function:

`maintenance_costs_sum([0, 2, 2, 0], [2, 1, 4, 3], [2, 3, 6, 5])`

The figure below shows the arrangement of bases and pathways on Planet X.

![image](https://hackmd.io/_uploads/BJh1DeIfA.png)


Calculating the maintenance cost for all possible $(i, j)$ pairs, the table below shows the results.

![image](https://hackmd.io/_uploads/Sk_lwg8fC.png)


The function should return $98$.

### Sample Grader

The Sample grader receives input in the following format:

Line 1: $N$
Line $2+i$ ($0 \leq i \leq N - 2$): $U[i]$ $V[i]$ $W[i]$

The Sample grader outputs the value returned by maintenance_costs_sum.

Note that the Sample grader may differ from the actual grader used for evaluation.