g6-07507. 树的重心 · 林老师的题库

题目描述

给定一棵以 $1$ 为根的有根树，共 $n$ 个结点。删去结点 $u$ （以及与之相连的边）后，原树会分成若干连通块。记 $M (u)$ 为这些连通块的最大结点数。

求 $M (u)$ 最小的结点 $u$ （并列时取编号最小者），并输出 $M (u)$ 。

第一行一个整数 $n$ 。

第二行 $n - 1$ 个整数 $f_{2}, f_{3}, \dots, f_{n}$ ，其中 $f_{i}$ 表示结点 $i$ 的父亲，保证 $f_{i} < i$ （ $n = 1$ 时该行为空）。

一行两个整数：结点编号与其对应的 $M (u)$ 。

输入：

4
1 2 3

输出：

2 2

链 $1 - 2 - 3 - 4$ ：删去 $2$ 号，剩下 ${1}$ 与 ${3, 4}$ ，最大块 $2$ ；删去 $3$ 号同理最大块 $2$ 。并列取编号小的 $2$ 号。

输入：

5
1 1 1 1

输出：

1 1

星形：删去中心 $1$ 号，剩下 $4$ 个孤立点，最大块 $1$ 。