给你一棵树 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。