균형 잡힌 트리 경로

시간 제한2초메모리 제한2048 MB

요약

트리에서 노드에 적힌 괄호를 경로 순서대로 이었을 때 균형 잡힌 문자열이 되는 경로의 개수를 구합니다.

난이도: 보통10점 중 6점
유형: 트리, DFS, 스택, 문자열
정답자: 아직 제출이 없습니다

문제

트리의 각 노드에는 ()[]{} 중 하나의 문자가 적혀 있다. 경로는 같은 노드를 두 번 포함하지 않고, 인접한 두 노드가 간선으로 연결된 노드들의 수열이며 길이는 1 이상이다. 경로에 속한 노드의 문자를 순서대로 이어 붙인 문자열이 균형 잡힌 문자열이면, 그 경로를 균형 잡힌 경로라고 한다.

문자열이 균형 잡혔는지는 다음 규칙으로 정한다.

빈 문자열은 균형 잡힌 문자열이다.
$s$ 가 균형 잡힌 문자열이면 $(s)$ , $[s]$ , $\{s\}$ 도 균형 잡힌 문자열이다.
$a$ 와 $b$ 가 균형 잡힌 문자열이면 두 문자열을 이은 $ab$ 도 균형 잡힌 문자열이다.

트리 전체에서 균형 잡힌 경로의 개수를 구하라.

입력

첫째 줄에 정수 $n$ ( $2 \le n \le 5 \cdot 10^3$ )이 주어진다.

둘째 줄에는 각 문자가 ()[]{} 중 하나인 길이 $n$ 의 문자열이 주어진다.

이어서 $n-1$ 개의 줄에 정수 $u$ 와 $v$ ( $1 \le u < v \le n$ )가 주어진다. 이는 노드 $u$ 와 $v$ 가 간선으로 연결되어 있다는 뜻이다. 주어지는 그래프는 트리이다.

출력

균형 잡힌 경로의 개수를 정수 하나로 출력한다.

예제3

예제 1
입력
```
4
()()
1 2
2 3
3 4
```
예상 출력
```
4
```
예제 2
입력
```
4
[[]]
1 2
2 3
3 4
```
예상 출력
```
2
```
예제 3
입력
```
6
([]{})
1 2
2 3
3 4
4 5
5 6
```
예상 출력
```
4
```