AT_ijpc2015_h 鉄道会社

### 题目背景 Sunuke住在一个有 $N$ 个车站的国家。在这个国家有两个铁路公司 $A$ 公司和 $B$ 公司，**两个公司的线路不共通**。 给定连接两个车站的线路 和 线路的长度 ，两家铁路公司都只使用自家的轨道 并且 直接连接两个车站的线路各自只会有最多一条。(**铁道是双向边 并且整个铁路网会形成一棵树**) 两个公司都只会使用自己公司的铁道，而车站 $i$ 和车站 $j$ 之间的票价是铁路网上它们之间的长度。 现在Sunuke在考虑 在不同的两个车站之间坐火车移动,乘坐哪个公司的车的代价会更小。 所以他找到了你并且想问你: 在整个铁路网中任意选取两座不同的车站时，满足乘两个铁路公司的车的票价一样 的车站对数。 ### 一句话题面 : 给定两棵节点数相同 且 有边权的树,求节点对 [$i,j$] 的数目,使得节点 $i$ 与节点 $j$ 之间的距离(也就是票价)在两棵树上相等。

第 $1$ 行:一个正整数表示 车站数目 $n$ 。 第 $2$ 行 到 第 $n$ 行:每行三个正整数 $u$ , $v$ , $w$ 表示在铁道公司 $A$ 的铁路网上, $u$ , $v$ 之间有长度为 $w$ 的直连铁道。 第 $n+1$ 行 到 第 $2n-1$ 行:每行三个正整数 $ u $ , $v$ , $w$ 表示在铁道公司 $B$ 的铁路网上, $u$ , $v$ 之间有长度为 $w$ 的直连铁道。

输出一个整数表示符合题意的节点对的数目。 注意行末需要换行。 ### 特殊性质(部分分) : 有 $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 ```

对于车站个数 $N$ ,满足$ 1 ≤ N ≤ 100000 $ 对于所有线路的长度 $p_i$ ,满足$ 1≤ p_i ≤ 10^9 $。 ###### 翻译: #uid 569422