Hide

Problem B
Balanced Tree Path

You are given a tree where each node is annotated with a character from ()[]{}. A path is a sequence of one or more nodes where no node is repeated and every pair of adjacent nodes is connected with an edge. A path is balanced if the characters at each node, when concatenated, form a balanced string. A string is balanced if it satisfies the following definition:

  • An empty string is balanced.

  • If s is a balanced string, then (s), [s], and {s} are balanced strings.

  • if a and b are balanced strings, then ab (a concatenated with b) is a balanced string.

Compute the number of balanced paths over the entire tree.

Input

The first line of input contains a single integer n (2n5103).

The next line contains a string of n characters, where each character is one of ()[]{}.

Each of the next n1 lines contains two integers, u and v (1u<vn), indicating that nodes u and v are connected with an edge. It is guaranteed the graph is a tree.

Output

Output a single integer, which is the number of balanced paths over the entire tree.

Sample Input 1 Sample Output 1
4
()()
1 2
2 3
3 4
4
Sample Input 2 Sample Output 2
4
[[]]
1 2
2 3
3 4
2
Sample Input 3 Sample Output 3
6
([]{})
1 2
2 3
3 4
4 5
5 6
4
Hide

Please log in to submit a solution to this problem

Log in