HMD02 - Cây phả hệ
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 2.0 giây
Giới hạn bộ nhớ: 32 megabyte
Đăng bởi: huynhduy_hmd

Trong quá trình nghiên cứu, các nhà khoa học đã phát hiện ra một loài mới và họ đặt tên nó là Humada. Họ tiến hành bắt về một con Humada để tiến hành nghiên cứu. Nhưng trớ trêu thay con vậy này sinh sản quá nhanh. Ngày càng đông và nguy hiểm, các nhà khoa học không thể quản lí nổi vì họ chỉ có thông tin về tên và ngày sinh của các con Humada. Bây giờ các nhà khoa học cần một cấu trúc dữ liệu đủ tốt để quản lí toàn bộ các sinh vật này. Và họ nghĩ ngay đến cây phả hệ. Các nhà khoa học tiến hành vẽ cây phả hệ bằng một trình soạn thảo văn bản đơn giản với những quy tắc sau:

  - Tên các con Humada sẽ được viết trong một khung hình chữ nhật tạo từ các kí tự '-', '|', 'o' và '+'. Dấu '+' chỉ được đặt ở chính giữa chiều rộng của hình chữ nhật, nếu chiều rộng chẵn thì dấu '+' đặt ở vị trí chính giữa bên trái. 

o--+--o

|anton|

o--+--o

o----+----o

|anamarija|

o----+----o

o-+--o

|pero|

o-+--o

 

Các hộp được liên kết với nhau bằng dấu '|'. Một liên kết có thể liên kết với nhiều hộp với những dấu '+' tương ứng. Các liên kết không được trùng.

+

|

o

|

+

+

|

o---o---o

|         |

+       +

+

|

o-----o-----o

|             |

+           +

 

Nếu tổ tiên có một đứa con duy nhất thì liên kết đơn được sử dụng. Ngược lại các nhà khoa học sẽ sử dụng liên kết phân nhánh. Với những đứa con lớn tuồi hơn ở bên trái. Liên kết phân nhánh có thể mở rộng theo chiều ngang với đảm bảo các đoạn kí tự '-' là bằng nhau.

Đừng lo lắng bạn sẽ không bị yêu cầu vẽ cây mà chỉ cần xác định số lượng kí tự được sử dụng.

Input:

 - Dòng đầu chứa số N (0<N<300001), là số lượng các con Humada.

 - N dòng tiếp theo chứa thông tin về các con Humada theo thứ tự sinh với con lớn tuổi nhất được đánh dấu 1, con mới sinh được đánh dâu N. Mỗi dòng chứa hai thông tin sau (trừ dòng 2 chứa thông tin về con đầu tiên) gồm:

 + Tên: chuỗi không lớn hơn 20 kí tự chứa các kí tự thường trong bảng chữ cái tiếng Anh.
 + Tổ tiên: Một số nguyên chỉ tổ tiên của con thứ i.

Output:

 - Một số nguyên duy nhất chỉ số kí tự tối thiểu cần sử dụng để vẽ cây phả hệ.

Ví dụ

  • input
    3
    adam
    kain 1
    abel 1
    output
    64
  • input
    12
    anton
    ana 1
    luka 1
    mia 2
    tea 3
    jakov 3
    semiramida 5
    dominik 5
    anamarija 4
    eustahije 4
    lovro 2
    lovro 11
    output
    371

Back to Top