Longest Non-decreasing Subsequence on Modified Tree Paths

You are given a rooted tree \(T\) with \(n\) nodes numbered from \(1\) to \(n\) with \(1\) as the root. Each node \(i\) has a color \(c_i\) (a lowercase letter between a and z) and an integer value \(P_i\).

For every node \(x\), consider all the simple paths that start at \(x\) and end at every node in the subtree of \(x\) (including \(x\) itself). In each such path the nodes appear in order from \(x\) toward a descendant. Now, modify each path originating from \(x\) as follows:

• If \(P_x = 1\), do not ignore any node.
• If \(P_x \ge 2\) and the path has at least \(P_x\) nodes, ignore (remove) the nodes in positions \(2, 3, \dots, P_x\). (If a path has fewer than \(P_x\) nodes then ignore all nodes except the first one.)

Thus, for a path \(x \to \dots \to y\) of length \(L\) (where \(L\ge1\)) the processed sequence is defined as:

[ S = \begin{cases} \bigl[c(x)\bigr] & \text{if } L < P_x+1,\ \bigl[c(x), c(u_{P_x+1}), c(u_{P_x+2}), \dots, c(y)\bigr] & \text{if } L \ge P_x+1, \end{cases} ]

Here, \(c(u)\) denotes the color of node \(u\). For each node \(x\) we define its answer as the maximum length of the longest non-decreasing subsequence (LNDS) among all the processed sequences corresponding to paths starting at \(x\). A subsequence is non-decreasing if for every two consecutive characters \(a\) and \(b\) in it, \(a \le b\) holds (the comparison is done in lexicographical order).

Your task is to compute and output the answer for every node \(x\) from \(1\) to \(n\).

inputFormat

The first line of input contains an integer \(n\) \((1 \le n \le 10^3)\) denoting the number of nodes.

The second line contains \(n\) integers: \(P_1, P_2, \dots, P_n\), where \(1 \le P_i \le n\).

The third line contains a string of length \(n\) consisting of lowercase letters; the \(i\)th character denotes \(c_i\).

Each of the next \(n - 1\) lines contains two integers \(u\) and \(v\) representing an edge between nodes \(u\) and \(v\). It is guaranteed that these edges form a tree with node \(1\) as the root.

outputFormat

Output a single line containing \(n\) space‐separated integers, where the \(i\)th integer is the answer for node \(i\).

sample

3
1 2 1
abc
1 2
1 3

2 1 1