Balanced Tree Path

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

요약

트리의 경로를 따라 노드 문자를 이어 붙였을 때 균형 잡힌 괄호 문자열이 되는 경로의 수를 센다.

난이도: 어려움10점 중 8점
유형: 트리, 동적 계획법, DFS, 조합론
정답자: 아직 제출이 없습니다

문제

You are given a tree where each node is annotated with a character from ()[]{}. A path is a sequence of one or more nodes where no node is repeated and every pair of adjacent nodes is connected with an edge. A path is balanced if the characters at each node, when concatenated, form a balanced string. A string is balanced if it satisfies the following definition:

An empty string is balanced.
If $s$ is a balanced string, then ( $s$ ), [ $s$ ], and { $s$ } are balanced strings.
if $a$ and $b$ are balanced strings, then $ab$ ( $a$ concatenated with $b$ ) is a balanced string.

Compute the number of balanced paths over the entire tree.

입력

The first line of input contains a single integer $n$ ( $2 \le n \le 5 \cdot 10^3$ ).

The next line contains a string of $n$ characters, where each character is one of ()[]\{\}.

Each of the next $n-1$ lines contains two integers, $u$ and $v$ ( $1 \le u < v \le n$ ), indicating that nodes $u$ and $v$ are connected with an edge. It is guaranteed the graph is a tree.

출력

Output a single integer, which is the number of balanced paths over the entire tree.

예제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
```