题目背景

译自 COI 2010 T3。

题目描述

南极的科学家发现了一种新生物！他们获取了一个样本到实验室进行繁殖。

他们很快注意到这种生物经常繁殖而且是单亲繁殖的。但每个个体最多繁殖两次，之后就会失去繁殖能力。

实验室中这种生物的个体数量迅速增加，需要绘制一份家谱。

他们打算把家谱画成如下的一棵树：

家谱以字符图形式表示，名字写在用符号 -、| 和 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$ 个小写英文字母组成的字符串。
• 亲代：一个整数，表示该生物的亲代的编号（第一个生物没有输入这个信息）。

输出格式

一行一个整数，表示最少需要多少个字符可以画下家谱。

3
adam 
kain 1 
abel 1 

64

12 
anton 
ana 1 
luka 1 
mia 2 
tea 3 
jakov 3 
semiramida 5 
dominik 5 
anamarija 4 
eustahije 4 
lovro 2 
lovro 11

371

提示

   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$。