Harry Potter and the Killing Curse
All submissions for this problem are available.
The Killing Curse was cast. Harry never expected this from Snape.
He wanted to save DumbleDore. He suddenly remembers a line from the Half Blood Prince's book about defeating the Killing curse.
It said "Calculate the power of the curse and use the exact same amount of the potion Elixir of Life to cure the affected". Next was the process of calculating the power of curse.
The Curse is combination of N mini curses arranged in the form of a weighted tree. Each node represents a mini curse and the weight of an edge between two mini curses defines the amount of dependency of these curses on each other. Power P of the curse is given by :
Where, Snodes = Set of all nodes of the Tree. X(u, v) = Minimum dependency of 2 adjacent mini curses present in the path from u to v. Y(u, v) = Maximum dependency of 2 adjacent mini curses present in the path from u to v.
Help Harry to calculate the Power P of the Killing curse, so that he can save DumbleDore. Since the Value of power can be arbitrarily large. Print P modulo (109 + 7).
- First line contains N number of nodes in the curse tree.
- Next N - 1 lines contains three integers each u, v, k denoting an edge of weight k between nodes u and v.
- It contains a single line, the value of P modulo (109 + 7).
- 1 ≤ N ≤ 105
- 1 ≤ u, v ≤ N
- 1 ≤ k ≤ 105
Input: 3 1 2 3 1 3 5 Output: 49
For the given tree in Example, values X(u, v) and Y(u, v) for all possible pairs is listed below.
- X(1,2) = 3 and Y(1,2) = 3
- X(1,3) = 5 and Y(1,3) = 5
- X(2,1) = 3 and Y(2,1) = 3
- X(2,3) = 3 and Y(2,3) = 5
- X(3,1) = 5 and Y(3,1) = 5
- X(3,2) = 3 and Y(3,2) = 5
Input: 5 1 2 3 1 3 5 2 4 7 2 5 2 Output: 174
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions