AT_indeednow_2015_finala_d Longest Path

Indeed 社非常重视 Speed 和 Price。 由于重视 Price，Indeed 社在全球的开发据点通过如下方式组成网络： 1. 部分通信线路只能单向通信。 2. 如果忽略所有通信线路的方向性，则任意两个据点之间恰好存在一条可以通过通信线路到达的路径。 满足以上条件的图结构为树结构。 由于也重视 Speed，员工们想知道在所有可以通信的据点中，中继据点数最多的两个据点是哪一对。 在这样的两个据点之间，中继的据点数是多少？

输入如下格式： > $n$ $a_1$ $b_1$ $t_1$ $a_2$ $b_2$ $t_2$ $\ldots$ $a_{n-1}$ $b_{n-1}$ $t_{n-1}$ - 第 $1$ 行为据点数 $n$，满足 $2 \leq n \leq 100,\!000$。 - 接下来的 $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$ 之间存在一条可以双向通信的线路。

请输出所求的值，输出一行。

由 ChatGPT 4.1 翻译