Bracket Paths

An expression is a string consisting only of properly paired brackets. For example, "()()" and "(()())" are expressions, whereas ")(" and "()(" are not. Expressions can be defined 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 of $n$ nodes numbered $1$ to $n$ and $n - 1$ edges, placed so that there is exactly one path between any two nodes. A single character is written in each node, and that character is either an open bracket "(" or a closed bracket ")". For different nodes $a$ and $b$, $w_{a,b}$ is the string obtained by walking the unique path from $a$ to $b$ and appending, one by one, the character written in each node you pass through. The string $w_{a,b}$ also contains the character of node $a$ (at the first position) and the character of node $b$ (at the last position).

Find the number of ordered pairs $(a, b)$ of different nodes such that $w_{a,b}$ is a correct expression. The string $w_{b,a}$ is the reverse of $w_{a,b}$, so $(a, b)$ and $(b, a)$ are counted separately.

The first line contains an integer $n$ ($1 \le n \le 300\,000$), the number of nodes in the tree.

The second line contains a string of $n$ characters, each of which is "(" or ")". The $j$-th character is the character written in node $j$.

Each of the next $n - 1$ lines contains two different integers $x$ and $y$ ($1 \le x, y \le n$), the labels of two nodes joined directly by an edge.

Print the number of such ordered pairs.