Description

Congcong and Keke are brothers who often fight over trivial things, such as when only one ice pop is left at home and they both want it, or they both want to use the computer (but there is only one). Normally they would resolve it with rock-paper-scissors, but they are bored of that simple game.

Their father, annoyed by their arguments, invented a new game: he draws $n$ “points” on paper and uses $n - 1$ “edges” to connect them so that the $n$ “points” are connected (this is a tree). Each “edge” has a number on it. Then Congcong and Keke each randomly choose one point (they cannot see the tree when choosing). If the sum of the numbers on all edges along the path between the two chosen points is a multiple of $3$, Congcong wins; otherwise, Keke wins.

Congcong likes thinking about problems. After each game, he carefully studies the tree and wants to know his winning probability for this graph. Please help compute this value to verify Congcong’s answer.

Input Format

The first line contains a positive integer $n$. The next $n - 1$ lines each contain $3$ integers $x, y, w$, indicating there is an edge between node $x$ and node $y$ with number $w$.

Output Format

Output the probability as an irreducible fraction in the form a/b, where $a$ and $b$ are coprime. If the probability is $1$, output 1/1.

5
1 2 1
1 3 2
1 4 1
2 5 3

13/25

Hint

Sample Explanation:

There are $13$ ordered pairs: $(1, 1)$, $(2, 2)$, $(2, 3)$, $(2, 5)$, $(3, 2)$, $(3, 3)$, $(3, 4)$, $(3, 5)$, $(4, 3)$, $(4, 4)$, $(5, 2)$, $(5, 3)$, $(5, 5)$.

Constraints:

For $100\%$ of the testdata, $n \leq 2 \times 10^4$.

Translated by ChatGPT 5