#P18076. Turtle Soup

Turtle Soup

Turtle Soup

题目描述

公司有 nn 名成员,编号为 11 到 nn,组织关系是一棵以 11 为根的树。成员 i>1i>1 的直属上级为 fif_i。

成员 aa 认识成员 bb,当且仅当至少满足以下一项:

  • a=ba=b;
  • bb 是 aa 的祖先;
  • bb 是 aa 的直接孩子。

认识关系不一定对称。

每轮游戏中,成员 mm 负责猜测目标 pp,保证 mm 不认识 pp。每次 mm 选择编号 xx,询问“pp 是否认识 xx?”,并得到真实回答。如果 x=px=p,还会明确告知目标就是 xx,游戏立即结束。

设依次询问 x1,x2,…x_1,x_2,\ldots。第一次询问的费用为 dis⁡(m,x1)\operatorname{dis}(m,x_1),后续第 ii 次询问的费用为 dis⁡(xi−1,xi)\operatorname{dis}(x_{i-1},x_i),其中距离是树上路径的边数。策略可以根据之前的回答决定下一次询问。

对每个 m=1,2,…,nm=1,2,\ldots,n,求保证游戏结束所需的最小最坏情况总费用。即使已经唯一确定目标,也必须实际询问 x=px=p 才算结束。若 mm 认识所有成员,答案为 00。

输入格式

第一行整数 nn;第二行 n−1n-1 个整数 f2,…,fnf_2,\ldots,f_n。

1≤n≤1051\le n\le10^5,1≤fi<i1\le f_i<i。当 n=1n=1 时,没有父节点数据。

输出格式

输出一行 nn 个整数,依次为每名成员作为猜测者时的答案。本题是标准输入输出题,无需进行交互。

样例 1

输入

3
1 1

输出

0 2 2

样例 2

输入

5
1 1 3 2

输出

4 3 3 4 4

样例 3

输入

6
1 1 2 2 3

输出

4 3 5 4 4 6