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

"()"는 표현식이다.
만약 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}가 올바른 표현식이 되는 경우의 쌍의 총 개수를 구하라.

#8234 upload 11 done 5 how_to_reg 4 call_split Subtarea

괄호 트리 timer 3s memory 1024MB

#8234
Subtarea

괄호 트리 3s 1024MB