Balanced Paths

You are given an undirected tree with $n$ nodes, numbered $1$ through $n$. Every node is labeled with either ( or ). For two nodes $u$ and $v$, let $l[u \to v]$ be the string obtained by concatenating the labels of the nodes on the simple path from $u$ to $v$, read in order from $u$ to $v$. On a tree the simple path between two nodes is unique.

A balanced string is defined as follows.

• The empty string is balanced.
• If $s$ is balanced, then the concatenation of (, $s$, ) is balanced.
• If $s$ and $t$ are balanced, then their concatenation $st$ is balanced.
• No other string is balanced.

Count the ordered pairs of nodes $(u, v)$ such that $l[u \to v]$ is balanced.

The first line contains an integer $n$ ($2 \le n \le 100000$), the number of nodes of the tree.

The second line contains a string of length $n$. Each character of the string is ( or ), and the $x$-th character is the label of node $x$.

Each of the next $n - 1$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$), meaning that node $a_i$ and node $b_i$ are joined by an edge. The given graph is a tree.

Print one line containing the number of ordered pairs $(u, v)$ such that $l[u \to v]$ is balanced.