← 返回题目列表

Codeforces · 601/D

D. 无环有机化合物

中文机器翻译题面 查看原题

给你一棵树 T,它有 n 个顶点(编号为 1 到 n),每个顶点都有一个字母。该树的根位于顶点 1。

让我们看看某个顶点 v 的子树 Tv。可以沿着从 v 开始到 Tv 中的某个顶点(可能是 v 本身)结束的每个简单路径读取字符串。我们将可以通过这种方式读取的不同字符串的数量表示为 $$\operatorname{dif}(v)$$。

另外,每个顶点 v 都分配有一个数字 cv。我们对最大值为 $$\mathrm{dif}(v) + c_v$$ 的顶点感兴趣。

您应该计算两个统计数据:$$\mathrm{dif}(v) + c_v$$ 的最大值以及具有最大值 $$\mathrm{dif}(v) + c_v$$ 的顶点 v 的数量。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 300 000) - 树的顶点数。

第二行包含 n 个空格分隔的整数 ci (0 ≤ ci ≤ 109)。

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

下面的 n - 1 行描述了树 T。每行都包含两个空格分隔的整数 u 和 v (1 ≤ u, v ≤ n),表示顶点 u 和 v 之间的一条边。

保证输入将描述一棵树。

输出

打印两行。

在第一行,在所有 1 ≤ i ≤ n 上打印 $$m = \max(\operatorname{dif}(i) + c_i)$$。

在第二行,打印 $$m = \operatorname{dif}(v) + c_v$$ 的顶点 v 的数量。

示例

输入 #1

10
1 2 7 20 20 30 40 50 50 50
cacabbcddd
1 2
6 8
7 2
6 2
5 4
5 9
3 10
2 5
2 3

输出 #1

51
3

输入 #2

6
0 2 4 1 1 1
raaaba
1 2
2 3
2 4
2 5
3 6

输出 #2

6
2

注意

在第一个示例中,树如下所示:

可以从各个顶点读取的字符串集是:

最后,$$\mathrm{dif}(v) + c_v$$ 的值为:

在第二个示例中,$$\operatorname{dif}(1..n)$$ 的值为 (5, 4, 2, 1, 1, 1)。 T2 中读取的不同字符串为 $$a、aa、aaa、ab$$;请注意,$$\alpha \alpha$$ 可以向下读取到顶点 3 或 4。