← 返回题目列表

AtCoder · indeednow_2015_finala_d

D. 最长路径

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

問題文

确实强调速度和价格。
由于我们重视价格,Indeed 在世界各地的开发基地通过以下网络连接起来。

  1. 某些通信路径仅允许单向通信。
  2. 如果忽略所有通信通道的方向,则任何 2 基地之间的通信路径上只有一条可以遵循的路径。

满足上述条件的图具有树结构。
因为我们非常注重速度,所以我们的员工在他们可以通信的所有基地中拥有最多数量的中继站。 2 我想知道基地。
这样的 2 点之间会有多少个中继点?


入力

输入按以下格式给出。

n
a_1 b_1 t_1
a_2 b_2 t_2
...
a_{n-1} b_{n-1} t_{n-1}
  • 1 行中显示碱基数 给出了 n ( 2 \leq n \leq 100{,}000)。
  • 2 续行 n-1 行提供有关连接底座的通信路径的信息。 这意味着存在一条可用于与
  • 1 \leq a_i, b_i \leq n, a_i \neq b_i
  • t_i = 1 时,a_i 减去 b_i 进行单向通信的通信路径。
  • t_i = 2 时,a_i 和 按字典顺序比较 b_i 表示存在可用于双向通信的通信路径。

出力

在一行中输出所需的值。


入力例1

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

出力例1

2

入力例2

8
2 1 1
2 5 1
8 2 1
3 8 1
4 2 2
7 4 1
4 6 1

出力例2

3