34756번 - 최강 테토 뚱뽭

뚱뽭은 트리 나라에 사는 정점의 개수가 $N$이고 루트가 $1$번 정점인 트리다. 정점의 번호는 $1$번부터 $N$번까지이고, 각 정점 $u$에는 여는 괄호 ( 또는 닫는 괄호 ) 중 하나가 배정되어 있다.

트리 나라에는 테토 정점과 테토 수치를 다음과 같이 정의한다.

정점 $u$를 시작으로 말단 정점까지 자식 방향으로 이동하며 방문하는 자식 정점의 괄호를 $u$의 괄호 뒤에 방문한 정점 순서대로 이어붙일 때, 올바른 괄호 문자열이 만들어질 수 있는 경우가 있으면 정점 $u$는 테토 정점이라고 한다. 그리고 트리의 테토 정점의 수를 테토 수치라고 한다.

뚱뽭은 자신을 에겐이라고 하는 주변 친구들에게 최강 테토임을 증명하고 싶어 자신의 테토 수치를 보여주려 한다. 뚱뽭의 트리 구조가 주어질 때, 뚱뽭의 테토 수치를 구해보자.

첫 번째 줄에 정점의 수 $N$이 주어진다. $(1 \le N \le 200\,000)$

두 번째 줄에 정점 $N$개의 괄호 정보가 공백으로 구분되어 정점의 번호 순서대로 주어진다. 여는 괄호 (는 $0$, 닫는 괄호 )는 $1$로 주어진다.

세 번째 줄부터 $N-1$개의 줄에 트리의 간선 정보 $u, v$가 공백으로 구분되어 주어진다. 이는 두 정점 $u,v$가 간선으로 연결되어 있음을 의미한다. $u,v$는 정수이고 같은 간선 정보는 주어지지 않는다. $(1 \le u,v \le N;$ $u \neq v)$

입력으로 주어지는 모든 수는 정수이고, 입력으로 주어지는 트리는 항상 올바른 트리임이 보장된다.

첫 번째 줄에 테토 수치를 출력한다.

올바른 괄호 문자열은 다음과 같이 정의한다.

• 빈 문자열은 올바른 괄호 문자열이다.
• S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이다.
• S와 T가 올바른 괄호 문자열이라면, ST도 올바른 괄호 문자열이다.