Background

Twenty-six points:

。 。 。 。 。 。 。 。 。 。 。 。 。

。 。 。 。 。 。 。 。 。 。 。 。 。

Making twenty-six points is really fun, and in order to make up four problems, this number-composition problem with only $26$ kinds of weights was created.

Problem Description

You are given a rooted tree $T$ with $n$ nodes, rooted at $1$. The $i$-th node has a color $c_i$, where ${\tt a} \le c_i \le {\tt z}$, and a value $P_i$.

For each node $x$, there is a path from it to every node in its subtree (note that the order is from itself to a node in its subtree), for a total of $\text{size of subtree}$ paths.

Now, ignore the $2$-nd to the $P_x$-th nodes on each of these paths. In particular, if $P_x = 1$, then no nodes are ignored. Treat the path after ignoring as a sequence, where the weight of each node in the sequence is the $c_i$ of the node on the path. For each node, find the maximum, over all its sequences, of the length of the longest non-decreasing subsequence.

Note: If a path $j$ has $len_j < P_x$ nodes, this is equivalent to ignoring all nodes on this path except the first node.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers $P_i$.

The third line contains $n$ lowercase letters $c_i$, with no spaces between characters.

Next $n - 1$ lines describe the tree $T$. Each line contains two integers $u, v$, meaning there is an edge between $u$ and $v$.

There may be extra spaces at the end of lines (use getchar() with caution).

Output Format

Output $n$ lines, the answer for each node, in order of increasing index.

7
2 1 1 9 8 5 1
zzabcad
1 2
2 3
3 4
3 5
5 6
5 7

3
3
3
1
1
1
1

12
1 2 2 4 1 3 4 3 1 4 3 1 
baabbbbbbbaa
4 6
5 7
1 2
12 10
8 2
10 11
5 9
10 3
2 3
4 3
4 5

5
4
3
1
2
1
1
1
1
1
1
1

Hint

Explanation of Sample 1:

The shape of the tree in the sample:

For node $1$: $P_1=2$.

The LNDS with the maximum length: acd.

Node $2$ is the same as node $1$.

For node $3$: $P_3=1$.

The LNDS with the maximum length: acd.

For $4, 5, 6, 7$, each of their sequences contains only the node itself, so output $1$.

Constraints

This problem uses Subtask scoring.

For $100\%$ of the testdata:

$1 \le n \le 10^5$.

$\forall 1 \le i \le n$, $c_i$ is a lowercase letter, and $1 \le P_i \le n$.

The given tree is connected and valid.

Translated by ChatGPT 5