P17789 佐伯沙弥香不是罪过

『咽下的话语，还在继续成长，总有一天会冲破胸口……』

##### 注意：本题字符串比较规则为特殊规则，与常规字典序不同。 给定一棵大小为 $n$ 的基环树，每个节点上有一个字符。 定义节点 $i$ 的**最小权值**为：从节点 $i$ 出发的所有简单路径构成的字符串中，最小的字符串的暗恋值。 ##### 字符串比较规则 设字符串 $s$ 长度为 $x$，字符串 $t$ 长度为 $y$。 $s < t$ 当且仅当满足以下任一条件： 1. 存在下标 $i \in [1,\min(x,y)]$，使得 $s_i < t_i$ 且对于 $j y$。 ##### 字符串暗恋值定义 对于长度为 $x$ 的字符串 $s$，其暗恋值为： $$ val = \left( \sum_{i=1}^x s_i \cdot 13331^{x-i} \right) \bmod 998244353 $$ ##### 任务要求 求出所有节点的最小权值并输出。

第一行一个整数 $n$ ，第二行 $n$ 个整数，表示每一个节点的字符 $a_i$，接下来 $n$ 行每行两个整数 $u$，$v$表示一条边

一行 $n$ 个整数，表示每一个节点的最小权值

无论如何，都断然不可将其忘记。 保证 $2 \le n \le 10^5$，$1 \le a_i \le 10^5$，**不保证**基环树上环大小不小于 $3$。