Задача . E. Дерево Фурукава Нагисы

Однажды Оказаки Томоя купил дерево на день рождения Фурукава Нагисы. Дерево было немного странное, у каждой вершины дерева было написано значение. Обозначим значение у i-й вершины переменной v_i. Теперь Фурукава Нагиса и Оказаки Томоя хотят сыграть в игру с деревом.

Пусть (s, e) — путь из вершины s к вершине e дерева, тогда можно записать последовательность значений вершин на пути (s, e) и обозначить эту последовательность как S(s, e). Определим функцию G от последовательности S(s, e) следующим образом. Предположим, что последовательность равна z₀, z₁...z_l - 1, где l — длина последовательности. Определим G(S(s, e)) = z₀ × k⁰ + z₁ × k¹ + ... + z_l - 1 × k^l - 1. Если путь (s, e) удовлетворяет , тогда путь (s, e) принадлежит Фурукава Нагисе, в противном случае он принадлежит Оказаки Томоя.

Считать, у кого больше путей, слишком легко, поэтому ребята хотят поиграть во что-то посложнее. Фурукава Нагиса выдвинула гипотезу:

• если пути (p₁, p₂) и (p₂, p₃) принадлежат ей, то и путь (p₁, p₃) тоже принадлежит ей;
• если пути (p₁, p₂) и (p₂, p₃) принадлежат Оказаки Томоя, то и путь (p₁, p₃) тоже принадлежит Оказаки Томоя.

Конечно, описанное выполняется не для всех троек (p₁, p₂, p₃). Итак, теперь Фурукава Нагиса хочет узнать, сколько троек (p₁, p₂, p₃) удовлетворяют ее условию — и это ваша задача.