Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ACM 2016 - Round #3Ended |
C - Strings Balanceados
Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)
Se tiene un árbol no dirigido de $N$ nodos, numerados de $1$ a $N$, donde cada nodo está etiquetado con '(' o con ')'.Se denota $l[u \rightarrow v]$ como la cadena que se obtiene de concatenar las etiquetas de los nodos en el camino simple de $u$ a $v$. Su tarea consiste en calcular el número de pares ordenados de nodos $(u,v)$ tal que $l[u \rightarrow v]$ es una cadena balanceada.
Una cadena balanceada es definida de la siguiente manera:
* La cadena vacía está balanceada.
* Si $s$ es una cadena balaneada, la cadena "(" $s$ ")" está balanceada.
* Si las cadenas $s$ y $t$ están balanceadas, la cadena $st$ (la concatenación de $s$ y $t$) está balanceada.
* Cualquier otra cadena es no balanceada.
Input
La entrada consiste de un único caso de prueba. La primera línea contiene un entero $n$ $(2 \leq n \leq 10^5)$, el número de nodos del árbol.
La siguiente línea contiene una cadena de longitud $n$, cada caracter es ‘(’ o ‘)’. El $i$-ésimo caracter de la cadena representa la etiqueta del nodo $i$. Cada una de las siguientes $n - 1$ líneas contiene dos enteros $a_i$ y $b_i$ $(1 \leq a_i, b_i \leq n)$, lo cual representa una arista entre los nodos $a_i$ y $b_i$.
Output
La cantidad de pares ordenados de nodos $(u, v)$ tal que la cadena $l[u \rightarrow v]$ está balanceada.