← 返回题目列表

AtCoder · ijpc2015_h

D. 铁路公司

中文机器翻译题面 查看原题

問題文

潜伏是 我住在一个拥有N车站的国家。在这个国家,A 公司和 只有 B 家铁路公司,每个公司都建造自己的轨道。

这些轨道连接两个车站,每条轨道都有长度。两家铁路公司在两个车站之间运行同一条轨道,仅使用自己的轨道。 2 请勿多次使用。此时,我们知道任意两个站点都恰好有一条这样的路线。

因此,两家公司都利用各自所建线路的特点,i 第 站 和 第 j 站之间的交通费用是您在相邻车站之间旅行时所经过的相邻车站之间距离的最大值。

Snuke 是不同的。 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
这满足部分点约束。