Subway Routes

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 0.6s
Memory limit: 16M

Problem types

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.

Input Specification

N \le 50\,000, 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 \le x, y \le N).

Output Specification

The number of unique subway routes that have the longest length.

Sample Input

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

Sample Output