Copiado al portapapeles
Descripción
En el estadio más grande de la ciudad hay $N$ jugadores distribuidos en distintas zonas. Las zonas están conectadas mediante caminos bidireccionales, y se sabe que cualquier par de zonas está conectado por un único recorrido simple; es decir, la red de caminos forma un árbol.
Cada jugador pertenece a uno de dos equipos:
- Bananitas FC
- Yapapa FC
Para cualquier par de zonas $(u, v)$ con $u \le v$, consideremos el camino simple que las conecta.
Diremos que este camino es favorable para Bananitas FC si el número de jugadores de Bananitas FC presentes en las zonas del camino es estrictamente mayor que el número de jugadores de Yapapa FC.
Tu tarea es determinar cuántos pares de zonas $(u, v)$ generan un camino favorable para Bananitas FC.
Entrada
La primera línea contiene un entero $N$, el número de zonas del estadio.
$N \le 10^5$.
Las siguientes $N - 1$ líneas contienen dos enteros $u$ y $v$, indicando que existe un camino entre las zonas $u$ y $v$.
La segunda línea contiene una cadena de longitud $N$. El carácter $i$-ésimo es:
- B si la zona $i$ contiene un jugador de Bananitas FC.
- Y si la zona $i$ contiene un jugador de Yapapa FC.
Salida
Imprime un único entero: la cantidad de pares $(u, v)$ con $u \le v$ tales que, en el camino simple entre $u$ y $v$, la cantidad de jugadores de Bananitas FC es estrictamente mayor que la cantidad de jugadores de Yapapa FC.
Ejemplo Entrada
5 1 2 1 3 3 4 3 5 BBYYB
Ejemplo Salida
7