Bessie looks out the barn door at the beautiful spring day and
thinks to herself, "I'd really like to enjoy my walk out to the
pastures for the tender spring grass." She knows that once she
leaves the barn, she will traverse a path for a while, take one of
two choices that lead to other paths, follow one of them, take one
of two other choices, and continue on until the path leads to a
verdant pasture.
She decides to make the set of path choices that enables her to
walk over the greatest number of cow paths on her way to breakfast.
Given the description of these paths, determine how many cow paths
she traverses, presuming that she commences choosing various paths
as soon as she leaves the barn.
The farm has P (1 <= P <= 1,000) pastures that are lead to by P-1
choice-nodes (range 1..P-1) connected by paths. From the barn (which
is node 1), only one set of path traversals exists to reach any
choice-node or pasture.
Consider this set of paths (lines), pastures ('%'), and the highlighted
('#') route to a pasture on the right:
% %
/ /
2----% 7----8----% 2----% 7####8----%
/ \ / \ # # # #
1 5----6 9----% 1 5####6 9----%
\ \ \ \ \ \ \ #
\ % % % \ % % %
\ \
3-----% 3-----%
\ \
4----% 4----%
\ \
% %
The pasture reached from choice-node 9 is one of two that enable
Bessie to traverse seven different cowpaths on the way to breakfast.
These are the 'furthest' pastures from node 1, the barn.
Three integers describe each node: Cn, D1, and D2. Cn is the
nodenumber (1 <= Cn <= P-1); D1 and D2 are the destinations from
that node (0 <= D1 <= P-1; 0 <= D2 <= P-1). If D1 is 0, the node
leads to a pasture in that direction; D2 has the same property.
POINTS: 100
PROBLEM NAME: stroll
INPUT FORMAT:
* Line 1: A single integer: P
* Lines 2..P: Line i+1 contains three space-separated integers that describe a choice-node: Cn, D1, and D2
SAMPLE INPUT:
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
INPUT DETAILS:
This input describes the example farm layout in the task description.
OUTPUT FORMAT:
* Line 1: A single integer that is the largest number of paths Bessie
can traverse on the way to the furthest pasture.
SAMPLE OUTPUT:
7
OUTPUT DETAILS:
1-2-5-6-7-8-9-P is one of the longest routes.
[Vietnamese Translation]
Bessie nhìn ra cửa kho trong ngày mùa xuân đẹp và nghĩ đến mình,
"Tôi thực sự muốn thích đi bộ ra các đồng cỏ cho mùa xuân cỏ mềm."
Cô ấy biết rằng khi cô ấy rời nhà kho, cô sẽ đi qua một con đường trong một chốc,
chọn một trong hai lựa chọn dẫn đến đường dẫn khác, làm theo một trong số đó,
chọn một trong hai sự lựa chọn khác, và tiếp tục cho đến khi con đường dẫn đến
một đồng cỏ xanh tươi.
Cô quyết định tạo một tập các lựa chọn con đường cho phép mình đi bộ
trên tuyến đường có số lượng đường đi lớn nhất để ăn sáng của cô.
Cho sự mô tả của những đường đi, hãy xác định có bao nhiêu đường đi của bò
mà cô ấy đi qua, coi như rằng cô bắt chọn đường đi khác nhau
ngay sau khi cô rời khỏi nhà kho.
Trang trại có P (1 <= P <= 1.000) đồng cỏ nên được dẫn đến bởi P-1 nút lựa
chọn(các nút trong 1.. P) nối với nhau bằng các đường đi. Từ nhà kho,
(do là nút 1), chỉ có một bộ các tuyến đường đi tồn tại để đạt được
bất kỳ nút lựa chọn hoặc đồng cỏ.
Hãy xem xét tập hợp các đường đi (đường thẳng), đồng cỏ ('%'), và các
tuyến đường ('#') nhấn mạnh đến một đồng cỏ bên phải:
% %
/ /
2----% 7----8----% 2----% 7####8----%
/ \ / \ # # # #
1 5----6 9----% 1 5####6 9----%
\ \ \ \ \ \ \ #
\ % % % \ % % %
\ \
3-----% 3-----%
\ \
4----% 4----%
\ \
% %
Các đồng cỏ đến từ nút lựa chọn 9 là một trong hai cho phép Bessie
đi qua bảy đường đi khác nhau của bò trên đường đi ăn sáng. Đây là những
đồng cỏ 'xa nhất' từ nút 1, nhà kho.
Ba số nguyên mô tả mỗi nút: Cn, D1, và D2. Cn là số hiệu nút (1 <= Cn <= P-1);
D1 và D2 là những điểm đến từ nút đó (nút 0 <= D1 <= P-1; 0 <= D2 <= P-1).
Nếu D1 là 0, các nút dẫn đến một đồng cỏ ở hướng đó; D2 có tính chất tương tự.
ĐIỂM: 100
TÊN BÀI: stroll
KHUÔN DẠNG DỮ LIỆU VÀO:
* Dòng 1: Một số nguyên dương: P
* Các dòng 2..P: dòng i+1 gồm 3 số nguyên miêu tả một nút chọn lựa: Cn, D1, và D2
DỮ LIỆU VÀO MẪU (tệp tin stroll.in):
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
CHI TIẾT DỮ LIỆU VÀO:
Đầu vào này mô tả cách bố trí trang trại ví dụ trong bản mô tả đề bài.
KHUÔN DẠNG KẾT QUẢ:
* Dòng 1: Một số nguyên duy nhất là số đường đi lớn nhất mà
Bessie có thể đi qua trên đường đến đồng cỏ xa nhất.
KẾT QUẢ MẪU (tệp tin stroll.out):
7
CHI TIẾT KẾT QUẢ:
1-2-5-6-7-8-9-P một tuyến đường dài nhất.
[Chinese Translation]
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也一樣。
分值: 100
題目名稱: stroll
輸入格式:
* 第1行: 一個單獨的整數: P
* 第2到第P行: 第i+1行有3個由空格隔開的整數，表示一個分岔節點Cn, D1和D2。
樣例輸入 (文件 stroll.in):
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
輸入細節:
這個輸入表示題目描述中的例子。
輸出格式:
* 第一行: 一個單獨的整數，表示Bessie去最遠的草地的路上最多可以走過的小徑的數目。
樣例輸出 (文件 stroll.out):
7
輸出細節:
1-2-5-6-7-8-9-P是最長的一條路徑之一。