#P2959. [USACO09OCT] 散步
[USACO09OCT] 散步
题目描述
Bessie透过牛棚的大门向外望去。发现今天是一个美丽的春季早晨。她想,“我真的好想好想沐浴着春风,走在草地之中,感受嫩草温柔地抚摸四蹄地的感觉。”她知道一旦她离开了牛棚,她将沿着一条小径走一段路,然后就会出现一个三岔路口,她必须在两条小径中选择一条继续走下去。然后她又会遇到更多的三岔路口,进行更多的选择,知道她到达一个青翠的牧场为止。
她决定作一个选择使得她在去吃早草的路途中可以走过最多的小径。给你这些小径的描述,求出Bessie最多可以走过多少条小径。假定Bessie一出牛棚就有2条路径,Bessie需要从中选择一条。
农场中有P-1 (1 <= P <= 1,000) 个分岔节点(范围是1..P),引向P片草地,它们之间由小径连接。对任意一个节点来说,只有一条从牛棚(被标记为节点1)开始的路径可以到达。
考虑下面的图。线段表示小径,"%"表示草地。右边的图中的"#"表示一条到达草地的高亮的路径。
% %
/ /
2----% 7----8----% 2----% 7####8----%
/ \ / \ # # # #
1 5----6 9----% 1 5####6 9----%
\ \ \ \ \ \ \ #
\ % % % \ % % %
\ \
3-----% 3-----%
\ \
4----% 4----%
\ \
% %
从分岔节点9到达的草地是两个可以让Bessie走过最多小径的草地之一。在去吃早草的路上Bessie将走过7条不同的小径。这些草地是离牛棚也就是节点1最“远”的。
由3个整数来表示每一个节点:Cn, D1和D2,Cn是节点的编号(1 <= Cn <= P-1); D1和D2是由该节点引出的两条小径的终点(0 <= D1 <= P-1; 0 <= D2 <= P-1)。如果D1为0,表示这条小径引向的是一片牧草地;D2也一样。
输入格式
*第1行:单个整数:P
*第2..P行:第i+1行包含三个空格分隔的整数,用于描述选择节点:Cn、D1和D2
输出格式
*第1行:一个整数,是贝西在去最远牧场的路上可以穿过的最大路径数。
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
提示
此输入描述了任务描述中的示例场布局。 1-2-5-6-7-8-9-P是最长的路线之一。