시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 1024 MB | 84 | 35 | 30 | 37.975% |
An expression is a string of consisting only of properly paired brackets. For example, “()()
” and “(()())
” are expressions, whereas “)(
” and “()(
“ are not. We can define expressions inductively as follows:
()
” is an expression.(
$a$)
” is also an expression.A tree is a structure consisting of $n$ nodes denoted with numbers from $1$ to $n$ and $n - 1$ edges placed so there is a unique path between each two nodes. Additionally, a single character is written in each node. The character is either an open bracket “(
” or a closed bracket “)
”. For different nodes $a$ and $b$, $w_{a,b}$ is a string obtained by traversing the unique path from $a$ to $b$ and, one by one, adding the character written in the node we’re passing through. The string $w_{a,b}$ also contains the character written in the node $a$ (at the first position) and the character written in the node $b$ (at the last position).
Find the total number of pairs of different nodes $a$ and $b$ such that $w_{a,b}$ is a correct expression.
The first line of contains the an integer $n$ — the number of nodes in the tree. The following line contains an $n$-character string where each character is either “)
” or “(
”, the $j$th character in the string is the character written in the node $j$. Each of the following $n - 1$ lines contains two different positive integers $x$ and $y$ ($1 ≤ x, y ≤ n$) — the labels of nodes directly connected with an edge.
Output the required number of pairs.
번호 | 배점 | 제한 |
---|---|---|
1 | 10 | $n ≤ 1\,000$ |
2 | 30 | $n ≤ 300\,000$, the tree is a chain — each node $x = 1, \dots , n-1$ is connected to node $x + 1$. |
3 | 60 | $n ≤ 300\,000$ |
4 (()) 1 2 2 3 3 4
2
5 ())(( 1 2 2 3 2 4 3 5
3
7 )()()(( 1 2 1 3 1 6 2 4 4 5 5 7
6
Olympiad > Croatian Highschool Competitions in Informatics > 2017 > Croatian Olympiad in Informatics 2017 4번