{"raw_statement":[{"iden":"background","content":"二十六点：\n\n> 。 。 。 。 。 。 。 。 。 。 。 。 。\n>\n> 。 。 。 。 。 。 。 。 。 。 。 。 。\n\n凑二十六点真好玩，而为了凑四道题，就有了这道权值只有 $26$ 种的凑数题。"},{"iden":"statement","content":"\n给你一棵有 $n$ 个结点的以 $1$ 为根的树 $T$，第 $i$ 个结点有一个颜色 $c_i$，${\\tt a} \\le c_i \\le {\\tt z}$，和一个值 $P_i$。\n\n对于每一个点 $x$，**从它到它子树中每一个点**（注意顺序是从它本身到子树中的点）都有一条路径，一共有子树的大小条路径。\n\n现在忽略掉这些路径中的第 $2$ 到第 $P_x$ 个的点，特别地，若 $P_x = 1$ 则不忽略任何点。将忽略后的路径当作一个序列，序列中每个点的权值为路径上点的 $c_i$，求**每一个点的所有序列最长不下降子序列长度的最大值**。\n\n注: 若有路径 $j$ 上的节点数 $len_j < P_x$，则相当于忽略这条路径上除第一个点外的所有点。\n"},{"iden":"input","content":"第一行一个整数 $n$。\n\n第二行 $n$ 个整数 $P_i$。\n\n第三行 $n$ 个小写字母 $c_i$，**字符与字符间没有空格**。\n\n接下来 $n - 1$ 行，描述树 $T$，每行两个整数 $u,v$，表示 $u,v$ 存在一条边。\n\n行末可能有多余空格（慎用 `getchar()`）。"},{"iden":"output","content":"输出 $n$ 行，表示每一个点的答案，按照编号从小到大输出。"},{"iden":"note","content":"\n\n### 样例一解释：\n\n样例中树的形态：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/6vbio7vo.png?x-oss-process=image/resize,h_450,m_lfit)\n\n对于 $1$ 号节点：\n$P_1=2$。\n\n|  序列| 权值 | 最长不下降子序列长度 | 最长不下降子序列 |\n| :----------: | :----------: | :----------: | :----------: |\n| 1 | z | 1 | z |\n| 1 3 | za | 1 |  z |\n| 1 3 4 |  zab | 2  | ab |\n| 1 3 5  |  zac | 2 |  ac   |\n| 1 3 5 6 |  zaca | 2  | ac |\n| 1 3 5 7 | zacd| 3 | acd  |\n\n长度最长的最长不降子序列：acd。\n\n$2$ 号节点和 $1$ 号节点同理。\n\n对于 $3$ 号节点：\n$P_3=1$。\n\n|  序列| 权值 | 最长不下降子序列长度 | 最长不下降子序列 |\n| :----------: | :----------: | :----------: | :----------: |\n| 3 | a | 1 | a |\n| 3 4 | ab | 1 |  ab |\n| 3 5  |  ac | 2  | ac |\n| 3 5 6  |  aca | 2 |  ac   |\n|3 5 7   |  acd | 3  |acd |\n\n长度最长的最长不降子序列：acd。\n\n对于 $4,5,6,7$，它的所有序列中都只有它自己一个点，所以输出 $1$。\n### 数据范围\n\n本题采用 Subtask 计分。\n\n| Subtask | Limit | Pts |\n| :-----------: | :-----------: | :-----------: |\n| 0 | $n \\le 100$ | 5 |\n| 1 | $n \\le 2000$ | 15 |\n| 2 | $\\forall 1 \\le i \\le n \\quad P_i=1$ | 30 |\n| 3 | Empty | 50 |\n\n对于 $100\\%$ 的数据：\n\n$1 \\le n \\le 10^5$。\n\n$\\forall 1 \\le i \\le n$， $c_i$ 为小写字母，$1 \\le P_i \\le n$。\n\n给出的树连通且合法。"}],"translated_statement":null,"sample_group":[["7\n2 1 1 9 8 5 1\nzzabcad\n1 2\n2 3\n3 4\n3 5\n5 6\n5 7","3\n3\n3\n1\n1\n1\n1\n"],["12\n1 2 2 4 1 3 4 3 1 4 3 1 \nbaabbbbbbbaa\n4 6\n5 7\n1 2\n12 10\n8 2\n10 11\n5 9\n10 3\n2 3\n4 3\n4 5\n","5\n4\n3\n1\n2\n1\n1\n1\n1\n1\n1\n1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}