Problem
Una vez que Konstantin, después de haber participado en la siguiente, ya la 13ª Olimpiada internacional, regresaba a casa en tren. Él, como siempre, se sentó y pensó en el significado de la vida, resolviendo simultáneamente problemas de programación. Después de un tiempo, Konstantin se quedó dormido, pero el problema es que, para poder despertar, ¡debe resolver el problema que ha aparecido en su cabeza y que lo atormenta!
Esta vez, Konstantin soñó con un árbol que inicialmente constaba de un solo vértice con el número 1. En el problema que planteó, gradualmente se agregaron nuevos vértices al árbol. En el i-ésimo segundo, se agregó al árbol un vértice con el número i+1, el cual quedó suspendido como un hijo del vértice p
i, y en el borde entre los vértices i+1 y p
i se escribió la letra c
i.
Cada camino desde la raíz del árbol hasta el vértice v corresponde a una cierta cadena obtenida al escribir los símbolos escritos en los bordes del camino actual en el orden desde la raíz hasta el vértice v. Konstantin se enfrentó a una tarea difícil a primera vista: después de cada adición de un nuevo vértice, contar la cantidad de cadenas únicas que comienzan en la raíz del árbol (vértice número 1) y terminan en algún otro vértice.
En su sueño, Konstantin no es un genio en absoluto, por lo que él mismo no puede resolver este problema. Ayuda a Konstantin a resolver el problema y despierta.
Entrada:
La primera línea contiene el número n: el número de solicitudes para agregar un nuevo nodo al árbol (1 <= n <= 300000).
Las siguientes n líneas describen solicitudes para agregar vértices. La i-ésima consulta se describe mediante los parámetros p
i (1 <= p
i <= i) y c
i, que significa que el vértice agregado con el número i+1 está suspendido del vértice con el número p
i como hijo, y el símbolo c
i está escrito en el borde resultante - una letra minúscula del alfabeto latino.
Salida:
Imprimir n líneas. En la línea i-ésima, imprima la respuesta al problema de Konstantin después de agregar el vértice i+1-ésimo.
Ejemplos:
| Entrada |
Salida |
2
1 b
2p |
1
2 |
3
1 o
1 o
2 j |
1
1
2 |