102742: [AtCoder]ABC274 C - Ameba
Description
Score : $300$ points
Problem Statement
You observed amoebae and kept some records.
Initially, there was one amoeba, numbered $1$.
You made $N$ records. According to the $i$-th record, the amoeba numbered $A_i$ disappeared by dividing itself into two new amoebae, which were then numbered $2i$ and $2i+1$.
Here, amoeba $A_i$ is said to be the parent of amoebae $2i$ and $2i+1$.
For each $k=1,\ldots,2N+1$, how many generations away is amoeba $k$ from amoeba $1$?
Constraints
- $1 \leq N \leq 2\times 10^5$
- The records are consistent. That is:
- $1\leq A_i \leq 2i-1$.
- $A_i$ are distinct integers.
Input
The input is given from Standard Input in the following format:
$N$ $A_1$ $A_2$ $\ldots$ $A_N$
Output
Print $2N+1$ lines. The $k$-th line should contain the generation distance between amoeba $1$ and amoeba $k$.
Sample Input 1
2 1 2
Sample Output 1
0 1 1 2 2
From amoeba $1$, amoebae $2$ and $3$ were born. From amoeba $2$, amoebae $4$ and $5$ were born.
- Amoeba $1$ is zero generations away from amoeba $1$.
- Amoeba $2$ is one generation away from amoeba $1$.
- Amoeba $3$ is one generation away from amoeba $1$.
- Amoeba $4$ is one generation away from amoeba $2$, and two generations away from amoeba $1$.
- Amoeba $5$ is one generation away from amoeba $2$, and two generations away from amoeba $1$.
Sample Input 2
4 1 3 5 2
Sample Output 2
0 1 1 2 2 3 3 2 2
Input
题意翻译
你有一棵树,起始时仅有一个根节点 $1$。 接下来有 $n$ 次操作。对于第 $i$ 次操作,编号为 $A_i$ 的节点将会增加两个儿子,编号分别为 $2i$ 和 $2i + 1$。 对于 $i=1,2,...,2N+1$,求节点 $i$ 到根节点的距离。Output
得分:300分
问题描述
你观察了变形虫并记录了一些信息。
最初,有一个变形虫,编号为1。
你记录了N次。根据第i次记录,编号为A_i的变形虫通过分裂成两个新的变形虫消失了,编号分别为2i和2i+1。
在这里,变形虫A_i被称为变形虫2i和2i+1的父代。
对于每个k=1,...,2N+1,变形虫k离变形虫1有多少代远?
约束条件
- 1≤N≤2×10^5
- 记录是连贯的。即:
- 1≤A_i≤2i-1。
- A_i是不同的整数。
输入
输入从标准输入以以下格式给出:
$N$ $A_1$ $A_2$ $\ldots$ $A_N$
输出
打印2N+1行。第k行应包含变形虫1和变形虫k之间的代数距离。
样例输入1
2 1 2
样例输出1
0 1 1 2 2
从变形虫1,变形虫2和3诞生。从变形虫2,变形虫4和5诞生。
- 变形虫1离变形虫1有0代远。
- 变形虫2离变形虫1有1代远。
- 变形虫3离变形虫1有1代远。
- 变形虫4离变形虫2有1代远,离变形虫1有2代远。
- 变形虫5离变形虫2有1代远,离变形虫1有2代远。
样例输入2
4 1 3 5 2
样例输出2
0 1 1 2 2 3 3 2 2