P7815 "Xiaowo R3" Self-Harm Colorless

> Just by someone like me being alive > Tens of thousands of people feel sad > No one wants me > If only it were a world like that > ——[Self-Harm Colorless](https://music.163.com/song?id=29124091)

You are given a tree with $n$ nodes, rooted at $1$, with edge weights. Define the path length $d(u,v)$ between two nodes $u, v$ on the tree as the sum of edge weights along the path from $u$ to $v$. For an unordered pair $(u,v)$, define a "tree triangle" if and only if all of the following hold: - Let $w$ be the lowest common ancestor of $u, v$. Then $w\neq u$ and $w\neq v$. - Using $d(u,w)$, $d(v,w)$, and some positive integer $x$ as side lengths, a triangle can be formed. The value $x$ can be chosen arbitrarily, so a pair $(u,v)$ may produce multiple tree triangles. In this case, $d(u,w)+d(v,w)+x$ is called the size of this tree triangle. See the sample explanation for a concrete example. Two tree triangles are considered different if **at least one** of the following conditions holds: - The unordered pair $(u,v)$ is different. - The size of the tree triangle is different. For a weighted tree $T$, define its sine value $\sin T$ as the ratio of: - the sum of sizes of all tree triangles in $T$, to - the total number of distinct tree triangles in $T$. Little H gives you $T$ and wants you to compute $\sin T$. To avoid precision issues, output the result modulo $10^9+7$. In particular, if there are no tree triangles in $T$, then $\sin T=0$.

The first line contains a positive integer $n$, the number of nodes in the tree. The next $n-1$ lines each contain three positive integers $u, v, w$, indicating that there is an edge of weight $w$ between nodes $u$ and $v$.

Output one line: the value of $\sin T$ modulo $10^9+7$. The testdata guarantees that the total number of distinct tree triangles in $T$ is not a multiple of $10^9+7$.

### Sample Explanation For sample 1, $T$ is shown in the figure below.  The triangle cycles formed by nodes $1,2,3$ are: $\underline{2,3},2;~\underline{2,3},3;~\underline{2,3},4$. The triangle cycles formed by nodes $1,3,4$ are: $\underline{3,3},1;~\underline{3,3},2;~\underline{3,3},3;~\underline{3,3},4;~\underline{3,3},5$. The triangle cycles formed by nodes $1,3,5$ are: $\underline{3,4},2;~\underline{3,4},3;~\underline{3,4},4;~\underline{3,4},5;~\underline{3,4},6$. The triangle cycle formed by nodes $2,4,5$ is: $\underline{1,2},2$. Sum of all triangle cycle sizes: $(7+8+9)+(7+8+\dots+11)+(9+10+\dots+13)+5=129$. Total number of triangle cycles: $3+5+5+1=14$. $\sin T=\dfrac{129}{14}$, and the result modulo $10^9+7$ is $214285725$. ### Constraints **This problem uses bundled testdata.** - Special Property A: There exists a node in $T$ with degree $n-1$. - Special Property B: Except for leaf nodes, every node has degree $2$. - Special Property C: $T$ is a perfect binary tree. | Subtask | Score | $1\le n\le $ | Special Property | | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $5$ | $3$ | None | | $2$ | $13$ | $10^3$ | None | | $3$ | $11$ | $7\times10^3$ | None | | $4$ | $17$ | $10^5$ | A | | $5$ | $17$ | $10^5$ | B | | $6$ | $17$ | $10^5$ | C | | $7$ | $20$ | $10^5$ | None | For all testdata, $1\le n\le 10^5$ and $1\le w\le 10^9$. ### Notes In the attached file `depression_sample.zip`: - `depression_sample1.in` is sample #1. - `depression_sample2.in` satisfies Special Property A. - `depression_sample3.in` satisfies Special Property B. - `depression_sample4.in` satisfies Special Property C. - `depression_sample5.in` does not satisfy any special property. Translated by ChatGPT 5