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