题目背景

二十六点：

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

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

凑二十六点真好玩，而为了凑四道题，就有了这道权值只有 $26$ 种的凑数题。

题目描述

给你一棵有 $n$ 个结点的以 $1$ 为根的树 $T$，第 $i$ 个结点有一个颜色 $c_i$，${\tt a} \le c_i \le {\tt z}$，和一个值 $P_i$。

对于每一个点 $x$，从它到它子树中每一个点（注意顺序是从它本身到子树中的点）都有一条路径，一共有子树的大小条路径。

现在忽略掉这些路径中的第 $2$ 到第 $P_x$ 个的点，特别地，若 $P_x = 1$ 则不忽略任何点。将忽略后的路径当作一个序列，序列中每个点的权值为路径上点的 $c_i$，求每一个点的所有序列最长不下降子序列长度的最大值。

注: 若有路径 $j$ 上的节点数 $len_j < P_x$，则相当于忽略这条路径上除第一个点外的所有点。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $P_i$。

第三行 $n$ 个小写字母 $c_i$，字符与字符间没有空格。

接下来 $n - 1$ 行，描述树 $T$，每行两个整数 $u,v$，表示 $u,v$ 存在一条边。

行末可能有多余空格（慎用 getchar()）。

输出格式

输出 $n$ 行，表示每一个点的答案，按照编号从小到大输出。

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

提示

样例一解释：

样例中树的形态：

对于 $1$ 号节点： $P_1=2$。

序列	权值	最长不下降子序列长度	最长不下降子序列
1	z	1	z
1 3	za
1 3 4	zab	2	ab
1 3 5	zac		ac
1 3 5 6	zaca
1 3 5 7	zacd	3	acd

长度最长的最长不降子序列：acd。

$2$ 号节点和 $1$ 号节点同理。

对于 $3$ 号节点： $P_3=1$。

序列	权值	最长不下降子序列长度	最长不下降子序列
3	a	1	a
3 4	ab		ab
3 5	ac	2	ac
3 5 6	aca
3 5 7	acd	3	acd

长度最长的最长不降子序列：acd。

对于 $4,5,6,7$，它的所有序列中都只有它自己一个点，所以输出 $1$。

数据范围

本题采用 Subtask 计分。

Subtask	Limit	Pts
0	$n \le 100$	5
1	$n \le 2000$	15
2	$\forall 1 \le i \le n \quad P_i=1$	30
3	Empty	50

对于 $100\%$ 的数据：

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

$\forall 1 \le i \le n$， $c_i$ 为小写字母，$1 \le P_i \le n$。

给出的树连通且合法。