J9 例题-2 悠闲的漫步

题目描述

一个美丽的春季早晨。奶牛苏西想离开牛棚，去找一个青翠的牧场饱餐一顿。 她将沿著一条小径走一段路，当来到一个三岔路口（来时有一条小路，前面有两个方向的小径可以选择），她必须在面前的两条小径中选择一条，然后继续走下去。 随后，当她遇到更多的三岔路口时，仍然选择前面的任意一个方向的小径，直到到达一个青翠的牧场為止。

已知农场中有 $n-1$ 个分叉路口（其中 $1$ 号路口就是牛棚），引向 $n$ 片牧场，它们之间由小径连接。对任意一个岔路口而言，只有一条路可以到达牛棚。

如下图所示：线段表示小径，%表示草地。右边的图中的#表示一条到达牧场的路径。

苏西希望得到您的帮助，使得她能到达牧场之前，经过尽可能多的路口（因为她享受选择的纠结感）。

输入格式

第一行一个整数 $n$ ；

接下来 $n-1$ 行，第 $i$ 行有 $3$ 个整数，第一个整数表示岔口节点的编号，接下来两个整数表示岔口通往的节点编号，如果此两个整数为 $0$，表示通往的是牧场而不是岔口节点。

输出格式

一个整数，表示奶牛苏西去到最远的牧场，路上最多可以走过的小径的数目。

样例输入

10
7 8 0
5 0 6
9 0 0
6 0 7
3 4 0
2 5 0
8 0 9
4 0 0
1 2 3

样例输出

7

样例分析

如上所述，奶牛苏西经过的岔口节点为 $8$ 个，路径是： $1-2-5-6-7-8-9-$牧场，所以是最长的一条路径，经过了 $7$ 个小径。

数据范围

对于 $100\%$ 的数据：$1 \le n \le 1000$。