Tree Diameter and Center
Given a tree represented by N nodes and N-1 edges, find the diameter of the tree and its center(s). The diameter is the longest path between any two nodes in the tree. The center of a tree is the node (or two nodes) that minimizes the maximum distance to any other node. For a path of length D, the center(s) are located at distance floor(D/2) and ceil(D/2) from one endpoint of a diameter path. If the diameter is D, and D is even, there is one center node. If D is odd, there are two center nodes. Print the length of the diameter, followed by the node indices (1-based) of the center(s) in increasing order.
Input
The first line contains an integer N. The next N-1 lines describe the edges, each containing two integers u and v, representing an edge between node u and node v (1-based indexing).
Output
Print the diameter length D, followed by the center node(s) (1-based indexing) in increasing order, separated by spaces.
Constraints
2 <= N <= 200000. The input describes a valid tree.
Example 1
5 1 2 1 3 2 4 2 5
3 1 2
Diameter is 3 (path 3-1-2-4 or 3-1-2-5). Center is node 2.
Example 2
6 1 2 2 3 3 4 4 5 5 6
5 3 4
Diameter is 5 (path 1-2-3-4-5-6). Centers are nodes 3 and 4.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 1 2 1 3 2 4 2 5
6 1 2 2 3 3 4 4 5 5 6