D - 鉄道会社

Contest Duration: 2015-11-23 13:30:00+0900 - 2015-11-23 18:30:00+0900 (local time) (300 minutes)

D - 鉄道会社 Editorial

Time Limit: 3 sec / Memory Limit: 256 MB

すぬけ君は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 点が与えられる。

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

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