|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|3 초||256 MB||9||6||5||62.500%|
You are given an undirected tree with n nodes. The nodes are numbered 1 through n. Each node is labeled with either ‘(’ or ‘)’. Let l[u → v] denote the string obtained by concatenating the labels of the nodes on the simple path from u to v. (Note that the simple path between two nodes is uniquely determined on a tree.) A balanced string is defined as follows:
Calculate the number of the ordered pairs of the nodes (u, v) such that l[u → v] is balanced.
The input consists of a single test case. The input starts with an integer n (2 ≤ n ≤ 105), which is the number of nodes of the tree. The next line contains a string of length n, each character of which is either ‘(’ or ‘)’. The x-th character of the string represents the label of the node x of the tree. Each of the following n − 1 lines contains two integers ai and bi (1 ≤ ai , bi ≤ n), which represents that the node ai and the node bi are connected by an edge. The given graph is guaranteed to be a tree.
Display a line containing the number of the ordered pairs (u, v) such that l[u → v] is balanced.
2 () 1 2
4 (()) 1 2 2 3 3 4
5 ()()) 1 2 2 3 2 4 1 5