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.

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

Loading...

View Submissions

Console