CF601D.Acyclic Organic Compounds

You are given a tree T with n vertices (numbered 1 through n) and a letter in each vertex. The tree is rooted at vertex 1.

Let's look at the subtree T__v of some vertex v. It is possible to read a string along each simple path starting at v and ending at some vertex in T__v (possibly v itself). Let's denote the number of distinct strings which can be read this way as .

Also, there's a number c__v assigned to each vertex v. We are interested in vertices with the maximum value of .

You should compute two statistics: the maximum value of and the number of vertices v with the maximum .

给你一棵有 $n$ 个顶点（编号为 $1$ 到 $n$）的树 $T$，每个顶点上标有一个字母。该树以顶点 $1$ 为根。

考虑某个顶点 $v$ 的子树 $T_v$。我们可以沿着每一条从 $v$ 出发、终点为 $T_v$ 中某个顶点（可以是 $v$ 自身）的简单路径读出一个字符串。记这样能读出的不同字符串的个数为 。

此外，每个顶点 $v$ 还被赋予一个数值 $c_v$。我们关注使得 取得最大值的那些顶点。

你需要计算两个统计量： 的最大值，以及使得 取得该最大值的顶点 $v$ 的个数。

The first line of the input contains one integer n (1 ≤ n ≤ 300 000) — the number of vertices of the tree.

The second line contains n space-separated integers c__i (0 ≤ c__i ≤ 109).

The third line contains a string s consisting of n lowercase English letters — the i-th character of this string is the letter in vertex i.

The following n - 1 lines describe the tree T. Each of them contains two space-separated integers u and v (1 ≤ u, v ≤ n) indicating an edge between vertices u and v.

It's guaranteed that the input will describe a tree.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 300\,000$）—— 树的顶点数。

第二行包含 $n$ 个用空格分隔的整数 $c_i$（$0 \leq c_i \leq 10^9$）。

第三行包含一个由 $n$ 个小写英文字母组成的字符串 $s$ —— 该字符串的第 $i$ 个字符表示顶点 $i$ 上的字母。

接下来的 $n-1$ 行描述树 $T$。每行包含两个用空格分隔的整数 $u$ 和 $v$（$1 \leq u, v \leq n$），表示顶点 $u$ 与顶点 $v$ 之间存在一条边。

保证输入描述的是一棵树。

Print two lines.

On the first line, print over all 1 ≤ i ≤ n.

On the second line, print the number of vertices v for which .

输出两行。

第一行，输出对所有 $1 ≤ i ≤ n$ 的 。

第二行，输出满足 的顶点 $v$ 的个数。

In the first sample, the tree looks like this:

The sets of strings that can be read from individual vertices are:

Finally, the values of are:

In the second sample, the values of are (5, 4, 2, 1, 1, 1). The distinct strings read in _T_2 are ; note that can be read down to vertices 3 or 4.

在第一个样例中，树的结构如下所示：

从各个顶点出发可读出的字符串集合为：

最终， 的值为：

在第二个样例中， 的值为 (5, 4, 2, 1, 1, 1)。在 _T_₂ 中可读出的不同字符串为 ；注意， 可沿路径向下读至顶点 3 或顶点 4。