Codeforces Round 333 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

dfs and similar

dsu

hashing

strings

trees

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Acyclic Organic Compounds

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou 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 .

Input

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} ≤ 10^{9}).

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.

Output

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 .

Examples

Input

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

Output

51

3

Input

6

0 2 4 1 1 1

raaaba

1 2

2 3

2 4

2 5

3 6

Output

6

2

Note

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.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/29/2023 11:10:08 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|