레이팅 미적용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.
• If \(a\) is an expression, then “(\(a\))” is also an expression.
• If \(a\) and \(b\) are expressions, then “\(ab\)” 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\), wa,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 \le x\), \(y \le n\)) — the labels of nodes directly connected with an edge.
Output the required number of pairs.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 10점 | \(n \le 1\,000\) |
2 | 30점 | \(n \le 300\,000\), the tree is a chain — each node \(x = 1\), . . . , \(n - 1\) is connected to node \(x + 1\). |
3 | 60점 | \(n \le 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