Weighted Tree Function
C++
Algorithms
Graph representation
Graphs
73.0% success
862 attempts
1s time
256MB memory
1024KB max code
You are given a weighted tree with \(N\) nodes and \(N - 1\) edges.
\(E\) is defined as \(\sum_\limits{i=1}^{i = N} \sum_\limits{j=i +1}^{j = N} F(i,j)\). Also, \(F(i, j)\) is equal to = (Maximum value of the edge that is present on the simple path between node \(i\) and \(j\)) \(\times i \times j\)
You are required to determine the value of \(E\) modulo \(10^9 + 7\).
Input format
- The first line contains an integer \(N\) denoting the number of nodes in a tree.
- The next \(N - 1\) lines contain three space-separated integers \(u, v, w\) denoting an edge between node \(u\) and \(v\) with weight \(w\).
Output format
Print the required value of \(E\) modulo \(10^9 + 7\).
Constraints
\(1 \le N \le 2 \times 10^5\)
\(1 \le w \le 10^6\)
\(1 \le u, v \le N\)
Examples
Input
3 1 2 10 1 3 2
Output
86
Explanation
- F(1,2) = 10*1*2
- F(1,3) = 2*1*3
- F(2,3) = 10*2*3
- E = F(1, 2) + F(1,3) + F(2,3) = 20 + 6 + 60 = 86
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 Editor...