P3478 [POI 2008] STA-Station

Given a tree with $n$ nodes, find a node such that when this node is chosen as the root, the sum of depths of all nodes is maximized. The depth of a node is defined as the number of edges on the simple path from that node to the root.

The first line contains an integer $n$, the number of nodes in the tree. The next $(n - 1)$ lines each contain two integers $u, v$, indicating that there is an edge connecting $u$ and $v$.

This problem uses Special Judge. Output one line with an integer, the index of the chosen node. If multiple nodes satisfy the requirement, output any one of them.

Sample 1 Explanation: Outputting $7$ or $8$ are both correct answers. Constraints: For all test points, it is guaranteed that $1 \leq n \leq 10^6$, $1 \leq u, v \leq n$, and the input is a tree. Translated by ChatGPT 5