P3478 [POI2008]STA-Station

admin

https://www.luogu.com.cn/problem/P3478

题目描述
给定一个 n 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。

一个结点的深度之定义为该节点到根的简单路径上边的数量。

输入格式
第一行有一个整数，表示树的结点个数 nn。
接下来 (n−1) 行，每行两个整数 u, v，表示存在一条连接 u, v 的边。

输出格式
本题存在 Special Judge。

输出一行一个整数表示你选择的结点编号。如果有多个结点符合要求，输出任意一个即可。

输入输出样例
输入 #1复制
8
1 4
5 6
4 5
6 7
6 8
2 4
3 4
输出 #1复制
7
说明/提示
样例 1 解释
输出 7 和 8 都是正确答案。

数据规模与约定
对于全部的测试点，保证 1≤n≤10^6,n1≤u,v≤n，给出的是一棵树。