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 .
输入描述:
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 ci (0 ≤ ci ≤ 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.
输出描述:
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
输入
10<br />1 2 7 20 20 30 40 50 50 50<br />cacabbcddd<br />1 2<br />6 8<br />7 2<br />6 2<br />5 4<br />5 9<br />3 10<br />2 5<br />2 3<br />6<br />0 2 4 1 1 1<br />raaaba<br />1 2<br />2 3<br />2 4<br />2 5<br />3 6<br />
输出
51<br />3<br />6<br />2<br />
备注:
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 T2 are ; note that can be read down to vertices 3 or 4.
加载中...