E. Expected Walk Maximization
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Alice initially has a weighted undirected tree $$$T$$$ of $$$n$$$ nodes and $$$n-1$$$ edges. Each edge has a positive integer weight.

Alice wants to design a route so that she can walk for as long as possible, but she does not want to walk forever. To do so, she chooses a direction for every edge of the tree. In other words, for each undirected edge $$$(u,v)$$$, she replaces it with exactly one of the directed edges $$$u\rightarrow v$$$ or $$$v\rightarrow u$$$, preserving its weight $$$w_{uv}$$$. This produces a directed graph $$$T'$$$.

After constructing $$$T'$$$, Alice chooses a starting vertex $$$r$$$ ($$$1\leq r\leq n$$$), and performs the following walk:

  • Suppose Alice is currently at vertex $$$u$$$.
  • If $$$u$$$ has no outgoing edge in $$$T'$$$, her walk ends.
  • Otherwise, she chooses one outgoing neighbour $$$v$$$ uniformly at random from all vertices $$$v$$$ such that $$$u\rightarrow v$$$ in $$$T'$$$, and traverses that edge.
Traversing an edge of weight $$$w$$$ adds $$$w$$$ to the total distance walked.

Over all possible choices of edge directions and the starting vertex $$$r$$$, help Alice maximize the expected total distance she walks, modulo $$$10^9 + 7$$$.

It can be shown that the answer can always be written as a fraction $$$\frac{P}{Q}$$$, where $$$Q \not\equiv 0 \pmod{10^9+7}$$$. Therefore, output the value $$$$$$ P\cdot Q^{-1} \text{ mod }(10^9 + 7) $$$$$$

Input

The first line of the input contains an integer $$$t$$$ ($$$1\leq t \leq 10^3$$$), the number of test cases. For each test case,

  • The first line contains an integer $$$n$$$ ($$$2\leq n \leq 10^5$$$) — the number of nodes.
  • The next $$$n-1$$$ lines contain three integers $$$u, v, w_{uv}$$$ ($$$1\leq u,v \leq n$$$, $$$u\neq v$$$, $$$1\leq w_{uv}\leq 10^9$$$).
Additional constraints on the input:
  • The sum of $$$n$$$ over all test cases will not exceed $$$2\times 10^5$$$.
  • There are no duplicate edges, and the edges are guaranteed to form a tree.
Output

For each test case, output a single integer on a line, denoting the maximum expected total distance she walks, modulo $$$10^9+7$$$. Note that the answer should be maximized before taking modulo $$$10^9 + 7$$$.

Example
Input
1
9
2 1 3
7 9 5
8 7 5
7 3 1
3 4 1
4 5 3
5 6 2
3 2 3
Output
12
Note

There is $$$1$$$ test case. One possible edge orientation is shown in the figure below.

Illustration of Sample Test Case. Visualization created using CSAcademy's graph editor.

When Alice starts from $$$r = 6$$$, she is forced to traverse $$$6\rightarrow 5 \rightarrow 4 \rightarrow 3$$$, contributing $$$2+3+1= 6$$$ to her expected distance.

From node $$$3$$$, she chooses node $$$2$$$ or node $$$7$$$ with probability $$$\frac{1}{2}$$$ each.

  • If she goes to node $$$2$$$, she is then forced to continue to node $$$1$$$, adding $$$3+ 3 = 6$$$
  • If she goes to node $$$7$$$, she then chooses node $$$8$$$ or node $$$9$$$ uniformly, so the expected distance is $$$1 + \frac{1}{2}\cdot 5 + \frac{1}{2} \cdot 5 = 6$$$

Therefore, the expected total distance is $$$$$$ 6+\frac{1}{2}\cdot 6 + \frac{1}{2}\cdot 6 = 12 $$$$$$ which can be shown to be the maximum expected total distance of her walk.