問題文

すぬけ君は$N$個の駅からなる国に住んでいる。この国では、$A$ 社と $B$ 社の鉄道会社だけがあり、それぞれが独自に線路を作っている。

これらの線路は二つの駅間を結んでおり、各線路には長さがある。どちらの鉄道会社も二つの駅の間を自社の線路だけを使って同じ線路を $2$ 回以上使わずに行く。このとき、どの二つの駅に対しても、そのような経路がそれぞれちょうど一通りずつあることが分かっている。

そこで、どちらの会社も自分の会社の作った線路の性質を生かして、$i$ 番目の駅と $j$ 番目の駅間の移動料金をその間を移動するときに通る隣り合った駅の間の距離の最大値としています。

すぬけ君は相異なる $2$ 駅間の移動に対して、どちらの鉄道会社を使った方がいいのか考えていました。そこで、何個かの相異なる駅間の移動ではどちらの鉄道会社を使っても料金が同じなのではないかと思い、そのような駅の組の数を求めようと思いました。

さて、いったい何通りの駅の組が料金が $2$ 社とも同じであったでしょうか。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $a_1$ $b_1$ $p_1$ $a_2$ $b_2$ $p_2$ ... $a_{N-1}$ $b_{N-1}$ $p_{N-1}$ $c_1$ $d_1$ $q_1$ $c_2$ $d_2$ $q_2$ ... $c_{N-1}$ $d_{N-1}$ $q_{N-1}$

• 一行目は駅の数 $N(1≦N≦100000)$ を表している。
• 続く $N-1$ 行は $A$ 社が作った線路の情報を表しており、$a_{i}(1≦a_{i}≦N)$ 番目の駅と $b_{i}(1≦b_{i}≦N)$ 番目の駅を結ぶ長さ $p_{i}(1≦p_{i}≦10^{9})$ の線路を $A$ 社が作ったことを表している。
• 続く $N-1$ 行は $B$ 社が作った線路の情報を表しており、$c_{i}(1≦c_{i}≦N)$ 番目の駅と $d_{i}(1≦d_{i}≦N)$ 番目の駅を結ぶ長さ $q_{i}(1≦q_{i}≦10^{9})$ の線路を $B$ 社が作ったことを表している。

配点

この問題には部分点がある。以下の制約を追加で満たすデータセットに正解した場合は 40 点が与えられる。

• 同じ鉄道会社は同じ長さの線路を作らない。

出力

どちらの鉄道会社を使っても料金が変わらないような駅の組の数を一行に出力せよ。改行を忘れないこと。

入力例$1$

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

出力例$1$

1

入力例$2$

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

出力例$2$

2

入力例$3$

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

出力例$3$

10
```これは部分点の制約を満たす。

* * *