Zagrade

문제

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 $aa$ is an expression, then “($aa$)” is also an expression.
• If $aa$ and $bb$ are expressions, then “$abab$” is also an expression.

A tree is a structure consisting of $nn$ nodes denoted with numbers from $11$ to $nn$ and $n-1n\; -\; 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 $aa$ and $bb$, $w_{a,b}w\_\{a,b\}$ is a string obtained by traversing the unique path from $aa$ to $bb$ and, one by one, adding the character written in the node we’re passing through. The string $w_{a,b}w\_\{a,b\}$ also contains the character written in the node $aa$ (at the first position) and the character written in the node $bb$ (at the last position).

Find the total number of pairs of different nodes $aa$ and $bb$ such that $w_{a,b}w\_\{a,b\}$ is a correct expression.

입력

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

출력

Output the required number of pairs.