Заочные олимпиады: Заочный этап

Дано дерево на \(n\) вершинах с корнем в вершине \(1\). В \(i\)-й вершине записан символ \(t_i\) - одна из трёх латинских букв a , b , c . Также дана строка \(s\) длины \(m\), состоящая из строчных латинских букв a , b , c .

Каждой паре вершин \((u, v)\) естественным образом можно сопоставить строку, которая получается последовательным выписыванием символов в вершинах на единственном простом пути от \(u\) до \(v\), начиная с символа в вершине \(u\).

Вам нужно посчитать количество пар целых чисел \((u, v)\) таких, что \(1\leq u,v\leq n\), и строка, соответствующая пути от \(u\) до \(v\), лексикографически меньше или равна \(s\).

Деревом называется связный граф, где у каждой вершины кроме первой (первая вершина называется корнем) задан единственный предок, с которым вершина соединена ребром. Путём в дереве между вершинами \(u\) и \(v\) называется такая последовательность вершин, в которой \(u\) — первая вершина, \(v\) — последняя, и любые 2 подряд идущие вершины соединены ребром. Путь называется простым, если никакая из вершин не встречается в нем дважды.

Строка \(a\) считается лексикографически меньше строки \(b\), если существует такое число \(k\), что на всех позициях меньших \(k\) строки \(a\) и \(b\) совпадают, а на \(k\)-й позиции символ строки \(a\) лексикографически меньше соответствующего символа строки \(b\), или же в том случае, если длина строки \(a\) меньше длины строки \(b\), а все символы на одинаковых позициях у строк совпадают.