497. Tree Power

0

Hard

The power of a tree is determined by finding the longest path in the tree where no adjacent nodes on the path have the same assigned character.
You are given a tree, represented as a connected, undirected graph with no cycles, rooted at node 0. The tree consists of n nodes numbered from 0 to n - 1.
The tree is represented by an array called parent, with size n, where parent[i] represents the parent of node i. The root node, 0, has a parent value of -1.
You are also given a string s of length n, where s[i] represents the character assigned to node i.
Find and return the power of the tree.

Input Format

The first line of the input should contain the value of n, which represents the number of nodes in the tree. The next line should contain a space-separated array called parent, with n elements, where parent[i] represents the parent of node i. The following line should contain a string s of length n, where s[i] represents the character assigned to node i.

Output Format

The output should be an integer representing the maximum power of the tree.

Example

Input

6 -1 0 0 1 1 2 abacbe Explanation:

Output

3

Constraints

  • The number of nodes in the tree, n, is equal to the length of the parent array and the length of the string s.
  • n is between 1 and 10^5, inclusive.
  • For all i greater than or equal to 1, the parent[i] value is between 0 and n - 1.
  • The parent[0] value is -1.
  • The parent array represents a valid tree.
  • The string s consists only of lowercase English letters.
    • Loading...

    View Submissions

    Console