← 返回题目列表

Codeforces · 1740/H

H. MEX 树操作

中文机器翻译题面 查看原题

给定一个有根树,将树中顶点 $$$u$$$ 的值递归地定义为其子节点值的 MEX$$$^\dagger$$$ 。请注意,这只是子级,而不是其所有后代。特别是,叶子的价值是$$$0$$$。

Pak Chanek 有一个有根树,最初只包含索引为 $$$1$$$ 的单个顶点,即根。 Pak Chanek 将进行 $$$q$$$ 查询。在第 $$$i$$$ 查询中,Pak Chanek 被赋予一个整数 $$$x_i$$$。 Pak Chanek 需要添加一个索引为 $$$i+1$$$ 的新顶点作为顶点 $$$x_i$$$ 的子顶点。添加新顶点后,Pak Chanek 需要重新计算所有顶点的值并报告当前树中所有顶点的值的总和。

$$$^\dagger$$$ 数组的 MEX(排除最小值)是不属于该数组的最小非负整数。例如,$$$[0,1,1,2,6,7]$$$ 的 MEX 为 $$$3$$$,$$$[6,9]$$$ 的 MEX 为 $$$0$$$。

输入

第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — 操作数。

接下来的 $$$q$$$ 行包含一个整数 $$$x_i$$$ ($$$1 \leq x_i \leq i$$$) — 第 $$$i$$$ 查询的描述。

输出

对于每个查询,打印一行,其中包含一个整数,表示添加顶点后树中所有顶点的新值之和。

示例

输入 #1

7
1
1
3
2
5
2
1

输出 #1

1
1
3
2
4
4
7

输入 #2

8
1
1
1
1
5
6
7
8

输出 #2

1
1
1
1
3
2
4
3

注意

在第一个示例中,第 $$$6$$$ 查询之后的树将如下所示。

- 顶点 $$$7$$$ 是叶子,因此其值为 $$$0$$$。
- 顶点 $$$6$$$ 是叶子,因此其值为 $$$0$$$。
- 顶点 $$$5$$$ 只有一个值为 $$$0$$$ 的子节点,因此其值为 $$$1$$$。
- 顶点 $$$4$$$ 是叶子,因此其值为 $$$0$$$。
- 顶点 $$$3$$$ 只有一个值为 $$$0$$$ 的子节点,因此其值为 $$$1$$$。
- 顶点 $$$2$$$ 的子节点的值为 $$$0$$$ 和 $$$1$$$,因此其值为 $$$2$$$。
- 顶点 $$$1$$$ 的子节点的值为 $$$1$$$ 和 $$$2$$$,因此其值为 $$$0$$$。

所有顶点的值之和为$$$0+0+1+0+1+2+0=4$$$。