Problem
Une fois, Konstantin, ayant participé à la prochaine, déjà la 13e Olympiade internationale, rentrait chez lui en train. Comme toujours, il s'est assis et a réfléchi au sens de la vie, résolvant simultanément des problèmes de programmation. Au bout d'un moment, Konstantin s'est assoupi, mais le problème, c'est que pour se réveiller, il doit résoudre le problème qui lui est venu à l'esprit et qui le hante !
Cette fois, Konstantin a rêvé d'un arbre qui se composait initialement d'un seul sommet avec le numéro 1. Dans le problème qu'il a posé, de nouveaux sommets ont été progressivement ajoutés à l'arbre. Dans la ième seconde, un sommet avec le numéro i+1 a été ajouté à l'arbre, qui a été suspendu en tant que fils du sommet p
i, et sur le bord entre les sommets i+1 et p
i la lettre c
i a été écrite.
Chaque chemin de la racine de l'arbre au sommet v correspond à une certaine chaîne obtenue en écrivant les symboles écrits sur les bords du chemin courant dans l'ordre de la racine au sommet v. Konstantin a fait face à une tâche difficile à première vue - après chaque ajout d'un nouveau sommet, compter le nombre de chaînes uniques commençant à la racine de l'arbre (sommet numéro 1) et se terminant à un autre sommet.
Dans son rêve, Konstantin n'est pas du tout un génie, il ne peut donc pas résoudre lui-même ce problème. Aidez Konstantin à résoudre le problème et réveillez-vous.
Saisie :
La première ligne contient le nombre n - le nombre de requêtes pour ajouter un nouveau nœud à l'arborescence (1 <= n <= 300000).
Les n lignes suivantes décrivent les demandes d'ajout de sommets. La ième requête est décrite par les paramètres p
i (1 <= p
i <= i) et c
i, qui signifie que le sommet ajouté avec le numéro i+1 est suspendu au sommet avec le numéro p
i en tant qu'enfant, et le symbole c
i est écrit sur l'arête résultante - une lettre minuscule de l'alphabet latin.
Sortie :
Imprimer n lignes. Sur la i-ème ligne, écrivez la réponse au problème de Konstantin après avoir ajouté le i+1-ème sommet.
Exemples :
| Entrée |
Sortie |
2
1 ch
2p |
1
2 |
3
1 o
1 o
2 j |
1
1
2 |