While taking the subway George, and Peter were determined to find the longest subway route. They found different routes, and declared their route to be the longest route. After arguing and missing their stop, they realized that both of their routes were the longest routes. Looking back at the map, George, and Peter want to find how many subway routes have the longest length. A subway route is considered different from another subway route if at least one of its endpoints is not an endpoint on the other route. It is guaranteed that there is exactly one unique path between any pair of stations. Assume that all tunnels between stations are of the same length.
N ≤ 50000, the number of stations. The next N-1 lines contain two unique integers x, and y, indicating there is a tunnel connecting stations x and y. (1 ≤ x,y ≤ N)
The number of unique subway routes that have the longest length.
10 5 7 7 1 6 1 2 1 2 8 1 9 3 9 10 9 4 9
Point Value: 17 (partial)
Time Limit: 1.00s
Memory Limit: 16M
Added: Aug 10, 2012
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
259 - 829 - 79 - 24 - 885 - 220 - 753 - 942 - 482 - 952 - 492 - 741 - 259
Other cases may also contain cycles, but I didn't check. Updated data would be nice! :(