| Codeforces Round 383 (Div. 1) |
|---|
| Закончено |
Если вдруг кто-то пропустил, у нас в стране Arpa чудесные девушки.
У Arpa есть подвешенное дерево (связный ациклический граф), состоящее из n вершин. Вершины пронумерованы от 1 до n, вершина 1 является корнем. На каждом ребре дерева написана некоторая буква. Mehrdad — фанат самовлюбленных вещей. Он называет строку самовлюбленной, если возможно переставить местами символы строки так, чтобы она стала палиндромом.
Он спросил Arpa про каждую вершину v, какая наибольшая длина среди простых путей в поддереве вершины v таких, что буквы на пути образуют самовлюбленную строку.
Первая строка содержит целое число n (1 ≤ n ≤ 5·105) — количество вершин в дереве.
Далее следует (n - 1) строка, i-я из них содержит целое число pi + 1 и букву ci + 1 (1 ≤ pi + 1 ≤ i, ci + 1 — строчная буква латинского алфавита, между a и v включительно), которые означают, что между вершинами pi + 1 и i + 1 есть ребро и на нем написана буква ci + 1.
Выведите n чисел. i-е из них должно быть равно наибольшей длине среди простых путей в поддереве вершины i таких, что буквы на пути образуют самовлюбленную строку.
4
1 s
2 a
3 s
3 1 1 0
5
1 a
2 h
1 a
4 h
4 1 0 1 0
