Problem
Una volta Konstantin, dopo aver partecipato alla successiva, già 13a Olimpiade internazionale, stava tornando a casa in treno. Lui, come sempre, si è seduto e ha pensato al significato della vita, risolvendo contemporaneamente problemi di programmazione. Dopo un po', Konstantin si è appisolato, ma il guaio è che, per svegliarsi, deve risolvere il problema che gli è venuto in mente e che lo perseguita!
Questa volta, Konstantin ha sognato un albero che inizialmente consisteva in un solo vertice con il numero 1. Nel problema che ha posto, nuovi vertici sono stati gradualmente aggiunti all'albero. Nell'i-esimo secondo, all'albero è stato aggiunto un vertice con il numero i+1, che è stato sospeso come figlio dal vertice p
i, e sullo spigolo tra i vertici i+1 e p
i è stata scritta la lettera c
i.
Ogni percorso dalla radice dell'albero al vertice v corrisponde a una certa stringa ottenuta scrivendo i simboli scritti sui bordi del percorso corrente nell'ordine dalla radice al vertice v. Konstantin ha affrontato un compito difficile a prima vista: dopo ogni aggiunta di un nuovo vertice, contare il numero di stringhe univoche che iniziano alla radice dell'albero (vertice numero 1) e terminano in un altro vertice.
Nel suo sogno, Konstantin non è affatto un genio, quindi lui stesso non può risolvere questo problema. Aiuta Konstantin a risolvere il problema e svegliati.
Inserimento:
La prima riga contiene il numero n - il numero di richieste per aggiungere un nuovo nodo all'albero (1 <= n <= 300000).
Le successive n righe descrivono le richieste per l'aggiunta di vertici. La query i-esima è descritta dai parametri p
i (1 <= p
i <= i) e c
i, che significa che il vertice aggiunto con numero i+1 è sospeso dal vertice con numero p
i come figlio, e il simbolo c
i è scritto sul bordo risultante - una lettera minuscola dell'alfabeto latino.
Uscita:
Stampa n righe. Sulla riga i-esima stampa la risposta al problema di Konstantin dopo aver aggiunto il vertice i+1-esimo.
Esempi:
| Input |
Uscita |
2
1 b
2p |
1
2 |
3
1 o
1 o
2j |
1
1
2 |