시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 1024 MB 16 13 11 84.615%

문제

An expression is a string of consisting only of properly paired brackets. For example, “()()” and “(()())” are expressions, whereas “)(” and “()(“ are not. We can define expressions inductively as follows:

  • “()” is an expression.
  • If a is an expression, then “(a)” is also an expression.
  • If a and b are expressions, then “ab” is also an expression.

A tree is a structure consisting of n nodes denoted with numbers from 1 to n and n − 1 edges placed so there is a unique path between each two nodes. Additionally, a single character is written in each node. The character is either an open bracket “(” or a closed bracket “)”. For different nodes a and b, wa,b is a string obtained by traversing the unique path from a to b and, one by one, adding the character written in the node we’re passing through. The string wa,b also contains the character written in the node a (at the first position) and the character written in the node b (at the last position).

Find the total number of pairs of different nodes a and b such that wa,b is a correct expression.

입력

The first line of contains the an integer n — the number of nodes in the tree. (1 ≤ n ≤ 300,000) The following line contains an n-character string where each character is either “)” or “(”, the j th character in the string is the character written in the node j. Each of the following n − 1 lines contains two different positive integers x and y (1 ≤ x, y ≤ n) — the labels of nodes directly connected with an edge.

출력

Output the required number of pairs.

예제 입력 1

4
(())
1 2
2 3
3 4

예제 출력 1

2

예제 입력 2

5
())((
1 2
2 3
2 4
3 5

예제 출력 2

3

예제 입력 3

7
)()()((
1 2
1 3
1 6
2 4
4 5
5 7

예제 출력 3

6