괄호 경로

식은 짝이 올바르게 맞는 괄호로만 이루어진 문자열이다. 예를 들어 "()()"와 "(()())"는 식이고, ")("와 "()("는 식이 아니다. 식은 다음과 같이 귀납적으로 정의할 수 있다.

• "()"는 식이다.
• $a$가 식이면 "($a$)"도 식이다.
• $a$와 $b$가 식이면 "$ab$"도 식이다.

트리는 $1$부터 $n$까지 번호가 붙은 $n$개의 정점과 $n - 1$개의 간선으로 이루어지며, 어느 두 정점 사이에도 경로가 정확히 하나 존재하는 구조이다. 각 정점에는 문자가 하나씩 적혀 있고, 그 문자는 여는 괄호 "(" 또는 닫는 괄호 ")"이다. 서로 다른 두 정점 $a$와 $b$에 대해 $w_{a,b}$는 $a$에서 $b$로 가는 유일한 경로를 따라가면서 지나는 정점에 적힌 문자를 차례대로 이어 붙인 문자열이다. $w_{a,b}$에는 정점 $a$의 문자(맨 앞)와 정점 $b$의 문자(맨 뒤)도 포함된다.

$w_{a,b}$가 올바른 식이 되는 서로 다른 정점의 순서쌍 $(a, b)$의 개수를 구하여라. $w_{a,b}$와 $w_{b,a}$는 서로 뒤집힌 문자열이므로 $(a, b)$와 $(b, a)$는 따로 센다.

첫째 줄에 트리의 정점 수 $n$이 주어진다. ($1 \le n \le 300\,000$)

둘째 줄에 길이가 $n$인 문자열이 주어진다. 각 문자는 "(" 또는 ")"이며, $j$번째 문자는 정점 $j$에 적힌 문자이다.

다음 $n - 1$개의 줄에는 각각 간선으로 직접 연결된 두 정점의 번호 $x$와 $y$가 주어진다. ($1 \le x, y \le n$, $x \ne y$)

조건을 만족하는 순서쌍의 개수를 출력한다.