812. 树的重心
时间限制：1000 MS 内存限制：64 MB
题目描述
## 题目描述 给定一颗树，树中包含 $n$ 个结点（编号 $1 \sim n$）和 $n-1$ 条无向边。 请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。 重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的**最大值最小**，那么这个节点被称为树的重心。 ## 输入格式 第一行包含整数 $n$，表示树的结点数。 接下来 $n-1$ 行，每行包含三个整数 $a$ 和 $b$，以及边权 $c$（此处默认为 $1$），表示点 $a$ 和点 $b$ 之间存在一条边。 ## 输出格式 输出一个整数 $m$，表示将重心删除后，剩余各个连通块中点数的最大值。 ## 数据范围 $1 \le n \le 10^5$ ## 输入 ```in1 9 1 2 1 1 7 1 1 4 1 2 8 1 2 5 1 4 3 1 3 9 1 4 6 1 ``` ## 输出 ```out1 4 ``` ## 提示