레이팅 미적용Scientists on Antarctica have found a new species! They extracted one sample and took it to the
laboratory for testing.
They quickly noticed the species reproduces quite often and that only one parent is required for
reproduction. However after the parent reproduces twice, it becomes sterile and cannot reproduce
again.
In spite of this the number of specimens in the laboratory skyrocketed and the need for family trees
appeared.
They decided to draw the tree in a simple text editor using following conventions:
The names of the specimens will be written inside nice boxes using characters '-', '|' and 'o'. The
center point of the upper and lower border will be marked by the character '+'. If the length of the
border is even, '+' will be on the left of the two center points.
o--+--o
|anton|
o--+--o
o----+----o
|anamarija|
o----+----o
o-+--o
|pero|
o-+--o
The boxes will be connected with links. One link connects two or more boxes on their respective '+'
characters, with the parent specimen placed above it's children. The boxes and links must not overlap.
+
|
o
|
+
+
|
o---o---o
| |
+ +
+
|
o-----o-----o
| |
+ +
If the parent has one child, a point to point (leftmost example) link is used. If the parent has two
children, a branching link is used, with the older child on the left, and the younger on the right.
Branching links may be expanded in the horizontal direction as long as the number of '-' characters on
both sides stays equal. Links cannot be expanded vertically.
Don't worry, you will not be asked to draw the tree, only determine the number of characters required
to draw it. Space characters are not counted, only '-', '|', '+' , 'o' and letters in the names.
Test data worth 50 points has \(N < 30\).
Test data worth 75 points has \(N < 3000\).
The first line of input contains one integer N (\(1 \le N \le 300\,000\)), number of specimens in the
laboratory.
The specimens are marked with numbers 1 to N in the order of birth, with the oldest marked 1 and
youngest marked N.
The next N lines contain birth notes of all specimens in the order of birth. Each specimen (except the
first whose parent is unknown) is described with two pieces of information:
na\(me - se\)quence of at most 20 lowercase english alphabet characters
parent – one integer denoting the parent of this specimen
The first and only line of input should contain the minimal number of characters needed to draw the
family tree.
3
adam
kain 1
abel 16412
anton
ana 1
luka 1
mia 2
tea 3
jakov 3
semiramida 5
dominik 5
anamarija 4
eustahije 4
lovro 2
lovro 11371
Sample description:
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
Counting the characters gives 64 and 371.