树的结点值

题目描述

给定一棵包含 \(n\) 个结点的树，树根编号为 \(1\)。定义第 \(i\) 个结点的值为：其子树中所有与 \(i\) 编号奇偶性相同的结点数量。请按编号从小到大输出每个结点的值。

注：编号奇偶性指结点编号是奇数还是偶数；例如 \(1,3,5\) 为奇，\(2,4,6\) 为偶。

输入格式

• 第一行包含一个整数 \(n\)。
• 接下来 \(n-1\) 行，第 \(i\) 行给出整数 \(F_{i+1}\)，表示结点 \((i+1)\) 的父结点编号。

输出格式

• 输出 \(n\) 行。第 \(i\) 行输出编号为 \(i\) 的结点的值。

样例 #1

输入

5
1
2
1
2

输出

3
1
1
1
1

说明/提示

• 对于 \(40%\) 的评测用例，\(1 \le n \le 5000\)；
• 对于所有评测用例，\(1 \le n \le 2 \times 10^5\)，\(1 \le F_i < i\)。