Subway Routes

View as PDF
Submit solution
Points: 12 (partial)
Time limit: 0.6s
Memory limit: 16M
Author:
Daniel_wcipeg
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

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

Sample Output

7

Comments