시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB17151386.667%

문제

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$, $w_{a,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 $w_{a,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 $w_{a,b}$ is a correct expression.

입력

The first line of contains the an integer $n$ — the number of nodes in the tree. 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.

서브태스크

번호배점제한
110

$n ≤ 1\,000$

230

$n ≤ 300\,000$, the tree is a chain — each node $x = 1, \dots , n-1$ is connected to node $x + 1$.

360

$n ≤ 300\,000$

예제 입력 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

채점 및 기타 정보

  • 예제는 채점하지 않는다.