P14215 [COI 2010] 家族 / LOZA
题目背景
译自 [COI 2010 T3](https://hsin.hr/hio2010/zadaci/)。
题目描述
南极的科学家发现了一种新生物！他们获取了一个样本到实验室进行繁殖。
他们很快注意到这种生物经常繁殖而且是单亲繁殖的。但每个个体最多繁殖两次，之后就会失去繁殖能力。
实验室中这种生物的个体数量迅速增加，需要绘制一份家谱。
他们打算把家谱画成如下的一棵树：
家谱以字符图形式表示，名字写在用符号 `-`、`|` 和 `o` 组成一个框内。框的上下边的中点用 `+` 标出。如果框的长度是偶数，那么 `+` 会标在两个中间位置的靠左一个。
:::align{center}
```
o--+--o o----+----o o-+--o
|anton| |anamarija| |pero|
o--+--o o----+----o o-+--o
```
:::
这些框会用一些边连起来。一组边可以将两个或多个盒子的 `+` 符号给连起来，父代的框在子代的上方。框和边都不能互相重叠。
:::align{center}
```
+ + +
| | |
o o---o---o o-----o-----o
| | | | |
+ + + + +
```
:::
如果一个父代生物只有一个子代，那么我们用最左侧的点到点的边把他们连起来。如果有两个子代，那么我们用有分支的边，**年长的子代生物在左侧，年幼的在右侧**。
分支的边可以在水平方向上无限伸长，但是要保证左右两侧的 `-` 字符是一样多的，但是**不能竖直伸长**。
别着急，你不用把这棵树真的画出来。你只需要求出来最少需要多少个字符就可以画出这样的树。**不计空格**，只计算 `-`、`|`、`+`、`o` 和它们的名字所需要的字符。
输入格式
第一行一个整数 $N$ $(1 \le N \le 300\ 000)$，表示实验室中的生物总数。
生物按照出生的顺序从 $1$ 到 $N$ 编号，最年长的是 $1$，最年幼的是 $N$。
接下来的 $N$ 行按照编号顺序给出了一个生物的信息。每一个生物都有如下两个信息：
- 名字：一个由不超过 $20$ 个小写英文字母组成的字符串。
- 亲代：一个整数，表示该生物的亲代的编号（第一个生物没有输入这个信息）。
输出格式
一行一个整数，表示最少需要多少个字符可以画下家谱。
说明/提示
```
o-+--o
|adam|
o-+--o
|
o--o--o
| |
o-+--oo-+--o
|kain||abel|
o-+--oo-+--o
```
```
o--+--o
|anton|
o--+--o
|
o------------o------------o
| |
o-+-o o-+--o
|ana| |luka|
o-+-o o-+--o
| |
o-------o-------o o--o--o
| | | |
o-+-o o--+--o o-+-oo--+--o
|mia| |lovro| |tea||jakov|
o-+-o o--+--o o-+-oo--+--o
| | |
o-----o-----o o o-----o-----o
| | | | |
o----+----o o----+----o o--+--oo----+-----o o---+---o
|anamarija| |eustahije| |lovro||semiramida| |dominik|
o----+----o o----+----o o--+--oo----+-----o o---+---o
```
可以数出字符数分别是 $64$ 和 $371$ 个。
对于 $50\%$ 的数据，有 $N < 300$。
对于 $75\%$ 的数据，有 $N < 3000$。