[Opoi 2024] 二十六点

二十六点： > 。 。 。 。 。 。 。 。 。 。 。 。 。 > > 。 。 。 。 。 。 。 。 。 。 。 。 。 凑二十六点真好玩，而为了凑四道题，就有了这道权值只有 $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 | z | | 1 3 4 | zab | 2 | ab | | 1 3 5 | zac | 2 | ac | | 1 3 5 6 | zaca | 2 | ac | | 1 3 5 7 | zacd| 3 | acd | 长度最长的最长不降子序列：acd。 $2$ 号节点和 $1$ 号节点同理。 对于 $3$ 号节点： $P_3=1$。 | 序列| 权值 | 最长不下降子序列长度 | 最长不下降子序列 | | :----------: | :----------: | :----------: | :----------: | | 3 | a | 1 | a | | 3 4 | ab | 1 | ab | | 3 5 | ac | 2 | ac | | 3 5 6 | aca | 2 | ac | |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$。 给出的树连通且合法。