#P18076. Turtle Soup
Turtle Soup
Turtle Soup
题目描述
公司有 名成员,编号为 到 ,组织关系是一棵以 为根的树。成员 的直属上级为 。
成员 认识成员 ,当且仅当至少满足以下一项:
- ;
- 是 的祖先;
- 是 的直接孩子。
认识关系不一定对称。
每轮游戏中,成员 负责猜测目标 ,保证 不认识 。每次 选择编号 ,询问“ 是否认识 ?”,并得到真实回答。如果 ,还会明确告知目标就是 ,游戏立即结束。
设依次询问 。第一次询问的费用为 ,后续第 次询问的费用为 ,其中距离是树上路径的边数。策略可以根据之前的回答决定下一次询问。
对每个 ,求保证游戏结束所需的最小最坏情况总费用。即使已经唯一确定目标,也必须实际询问 才算结束。若 认识所有成员,答案为 。
输入格式
第一行整数 ;第二行 个整数 。
,。当 时,没有父节点数据。
输出格式
输出一行 个整数,依次为每名成员作为猜测者时的答案。本题是标准输入输出题,无需进行交互。
样例 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