페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8234
서브태스크

괄호 트리 3s 1024MB

문제

표현식은 올바르게 짝지어진 괄호들로만 이루어진 문자열이다. 예를 들어, "()()"와 "(()())"는 표현식이지만, ")("와 "()("는 표현식이 아니다. 표현식은 다음과 같은 규칙을 통해 재귀적으로 정의된다.

  • "()"는 표현식이다.

  • 만약 a가 표현식이라면, "(a)"도 표현식이다.

  • 만약 a와 b가 표현식이라면, "ab"도 표현식이다.

트리는 n개의 노드로 이루어진 구조로, 각 노드는 1부터 n까지의 숫자로 표시된다. 트리는 n - 1개의 간선을 가지며, 임의의 두 노드 사이에 유일한 경로가 존재한다. 각 노드에는 한 개의 문자만 적혀 있으며, 이 문자는 열린 괄호 "(" 또는 닫힌 괄호 ")" 중 하나이다. 서로 다른 두 노드 a와 b에 대해, w_{a,b}는 노드 a에서 b까지의 유일한 경로를 따라 지나가는 노드들에 적힌 문자를 순서대로 추가해 만든 문자열이다. 이때, w_{a,b}는 노드 a와 노드 b에 적힌 문자도 포함한다.

서로 다른 노드 a와 b에 대해, w_{a,b}가 올바른 표현식이 되는 경우의 쌍의 총 개수를 구하라.


입력

첫 번째 줄에는 정수 n이 주어진다. 이는 트리의 노드 개수이다. 두 번째 줄에는 n개의 문자로 이루어진 문자열이 주어지며, 각 문자는 열린 괄호 "(" 또는 닫힌 괄호 ")"이다. 문자열의 j번째 문자는 노드 j에 적힌 문자이다. 그다음 n - 1개의 줄에는 두 개의 서로 다른 정수 x와 y가 주어지며 (1 ≤ x, y ≤ n), 이는 직접 연결된 두 노드의 번호를 나타낸다.


출력

주어진 조건을 만족하는 쌍의 총 개수를 출력한다.


부분문제

번호 점수 조건
#110점

n ≤ 1\,000

#230점

n ≤ 300\,000, 트리는 체인 형태 — 각 노드 x = 1, \dots, n-1은 노드 x + 1과 연결된다.

#360점

n ≤ 300\,000


예제 #1

4
(())
1 2
2 3
3 4
2

예제 #2

5
())((
1 2
2 3
2 4
3 5
3

예제 #3

7
)()()((
1 2
1 3
1 6
2 4
4 5
5 7
6

출처

Croatian Olympiad in Informatics 2017
로그인해야 코드를 작성할 수 있어요.