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
成为编程大师，不再是梦想！全网最全C++题库，助您开启编程新篇章。标签： HBC24848最优的连续子段 数据结构 线段树[USACO 2009 Oct G]The Leisurely Stroll题解
