D - Longest Path Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

Indeed 社は、Speed と Price を重視している。
Price を重視しているため、世界中に存在する Indeed 社の開発拠点は次のようなネットワークでつながれている。

  1. 一部の通信路は単方向通信しかできない。
  2. 全ての通信路の向きを無視した場合、任意の 2 拠点間において、通信路をたどって行けるようなパスがちょうど一つ存在する。

以上の条件を満たすグラフは木構造になる。
Speedも重視しているため、社員らは通信できる拠点のなかで最も中継する拠点数が多い 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