균형 잡힌 경로

정점이 $n$개인 무방향 트리가 주어진다. 정점 번호는 $1$번부터 $n$번까지다. 각 정점에는 ( 또는 )가 하나씩 적혀 있다. 두 정점 $u$, $v$에 대해 $l[u \to v]$는 $u$에서 $v$로 가는 단순 경로 위의 정점에 적힌 문자를 $u$부터 $v$까지 순서대로 이어 붙인 문자열이다. 트리에서 두 정점을 잇는 단순 경로는 유일하다.

균형 잡힌 문자열은 다음과 같이 정의한다.

• 빈 문자열은 균형 잡힌 문자열이다.
• $s$가 균형 잡힌 문자열이면 (, $s$, )를 순서대로 이어 붙인 문자열도 균형 잡힌 문자열이다.
• $s$와 $t$가 균형 잡힌 문자열이면 둘을 이어 붙인 $st$도 균형 잡힌 문자열이다.
• 그 밖의 문자열은 균형 잡힌 문자열이 아니다.

$l[u \to v]$가 균형 잡힌 문자열인 순서쌍 $(u, v)$의 개수를 구하라.

첫째 줄에 트리의 정점 개수 $n$이 주어진다. ($2 \le n \le 100000$)

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

다음 $n - 1$개 줄에는 두 정수 $a_i$와 $b_i$가 주어진다. ($1 \le a_i, b_i \le n$) 정점 $a_i$와 정점 $b_i$가 간선으로 이어져 있다는 뜻이다. 주어지는 그래프는 항상 트리다.

$l[u \to v]$가 균형 잡힌 문자열인 순서쌍 $(u, v)$의 개수를 한 줄에 출력한다.