AT_arc028_3.[ARC028C] 高橋王国の分割統治

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

高桥王国由 $N$ 个城镇组成，每个城镇编号从 $0$ 到 $N-1$ 。另外，有 $N-1$ 条道路连接这些城镇，保证任意两个城镇之间都可以通过若干条道路互相到达。

高桥王国的国王高桥君正在决定哪个城镇作为首都。为了参考，他决定计算每个城镇作为首都时的“平衡值”。当选择城镇 $v$ 作为首都时，其“平衡值”定义为：在不经过城镇 $v$ 的情况下，能够互相到达的城镇集合中，最大集合的大小。

例如，下图中当选择城镇 $1$ 作为首都时，{城镇 $0$ , 城镇 $4$ }、{城镇 $2$ }、{城镇 $3$ } 等集合都可以在不经过城镇 $1$ 的情况下互相到达。其中最大集合为 {城镇 $0$ , 城镇 $4$ }，其大小为 $2$ ，因此城镇 $1$ 作为首都时的“平衡值”为 $2$ 。

输入格式

输入通过标准输入给出，格式如下：

$N$
$p_1$
$p_2$
$\vdots$
$p_{N-1}$

第 $1$ 行为一个整数 $N\ (1 \leq N \leq 100,\!000)$ ，表示城镇的数量。
接下来的 $N-1$ 行，每行一个整数 $p_i\ (0 \leq p_i \leq i-1)$ ，表示存在一条道路连接城镇 $i$ 和城镇 $p_i$ 。

输出格式

输出共 $N$ 行。第 $i$ 行输出一个整数，表示选择城镇 $i-1$ 作为首都时的“平衡值”。

输入输出样例

输入#1
```
5
0
1
1
0
```
输出#1
```
3
2
4
4
4
```
输入#2
```
3
0
0
```
输出#2
```
1
2
2
```

说明/提示

部分分

本题设有部分分。

若能通过所有 $N \leq 1000$ 的测试点，将获得 $30$ 分。

样例解释 1

本样例的输入对应于题目描述中的示意图。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页