Balanced Tree Path

Time limit2sMemory limit2048 MB

Summary

Count the paths in a tree whose node labels, read in path order, form a balanced bracket string.

Level: Medium6 of 10
Topics: Tree, DFS, Stack, String
Solved: No attempts yet

Problem

Each node of a tree is labeled with one of the characters ()[]{}. A path is a sequence of one or more nodes in which no node repeats and every pair of adjacent nodes is joined by an edge. A path is balanced if the characters of its nodes, concatenated in order, form a balanced string.

A string is balanced by these rules:

The empty string is balanced.
If $s$ is balanced, then $(s)$ , $[s]$ , and $\{s\}$ are balanced.
If $a$ and $b$ are balanced, then the concatenation $ab$ is balanced.

Count the balanced paths in the whole tree.

Input

The first line contains an integer $n$ ( $2 \le n \le 5 \cdot 10^3$ ).

The second line contains a string of $n$ characters, each one of ()[]{}.

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

Output

Print a single integer: the number of balanced paths.

Examples3

Example 1
Input
```
4
()()
1 2
2 3
3 4
```
Expected output
```
4
```
Example 2
Input
```
4
[[]]
1 2
2 3
3 4
```
Expected output
```
2
```
Example 3
Input
```
6
([]{})
1 2
2 3
3 4
4 5
5 6
```
Expected output
```
4
```