All Tracks Algorithms Graphs Depth First Search Problem

Explorer's Birthday
Tag(s):

Algorithms, Medium

Problem
Editorial
Analytics

Today is Explorer's birthday, and two of his best friends Raful and Jambo gave him a tree with $$N$$ vertices and $$N-1$$ edges. After playing with it for a while, Explorer got bored, so Raful and Jambo gave him a task:

find the answer $$A$$ modulo $$10^9 + 7$$ - sum of all functions $$f(u, v)$$ for all unordered pairs of vertices $$(u, v)$$ such that $$u != v$$. The function $$f(u ,v)$$ is the product of the weights of the edges on the shortest path between $$u$$ and $$v$$. Note that pairs $$(u, v)$$ and $$(v, u)$$ are considered the same, so must only be counted once.

He easily solved it. Can you (the best programmer in Lalalandia) do it too?

Input format

The first line contains one integer $$N$$ - the number of vertices.

The next $$N-1$$ lines describe the edges: each contains three integers $$u$$, $$v$$ and $$c$$. This means that there is the edge with weight $$c$$ between vertices $$u$$ and $$v$$.

Output format

The first line should contain the single integer $$A$$ modulo $$10^9 +7$$ - sum of all functions $$f(u, v)$$.

Constraints:

$$1 \le N \le 5 * 10^5$$

$$1 \le u, v \le N$$

$$1 \le c \le 10^9$$

SAMPLE INPUT
4
1 2 2
2 3 3
1 4 1
SAMPLE OUTPUT
20
Explanation

There are $$6$$ unordered unique pairs: $$(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)$$, so the answer is $$2 + 6 + 1 + 3 + 2 + 6 = 20$$.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

HackerEarth Collegiate Cup Second Elimination

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications