Tree of Life

View as PDF

Submit solution


Points: 20 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

You are a biologist studying an evolutionary tree. An evolutionary tree is a rooted tree showing the evolutionary relationships between several species. There are N nodes numbered 1 to N, each of which represents a different species. The tree is rooted from node 1. Two species are said to be distant if neither of their corresponding nodes are descendants of the other.

You have collected the DNA sequences of all N species in your evolutionary tree. The DNA of the species of node i is represented as a string S_i composed of the characters A, C, G, and T for 1\le i \le N. The genetic similarity of two species is the length of the longest common substring of their DNA sequences.

Find the largest genetic similarity between two distant species.

Constraints

S is the sum of the lengths of the N DNA sequences collected.

Subtask 1 [20%]

1\le N\le 20\ 000
1\le S\le 100\ 000
All DNA sequences only contain A.

Subtask 2 [80%]

1\le N\le 20\ 000
1\le S\le 100\ 000

Input Specification

The first line contains a single integer N.
The next N-1 lines each contain a single integer. These integers represent the tree. The integer on the i^{\text{th}} of the N-1 lines represents the node which is the parent of the node i+1. For convenience, it is guaranteed that this number is less than i+1.
The next N lines each contain a string composed of G, C, A, or T. The string on the i^{\text{th}} of the N lines is S_i, the DNA of the species represented by node i.

Output Specification

Output a single integer, the largest genetic similarity between two distant species. If there are no two distant species, output -1.

Sample Input 1

3
1
2
ACT
GG
AGG

Sample Output 1

-1

Sample Input 2

3
1
1
ACT
GG
AGG

Sample Output 2

2

Comments

There are no comments at the moment.