| Codeforces Round 248 (Div. 1) |
|---|
| Закончено |
Однажды Оказаки Томоя купил дерево на день рождения Фурукава Нагисы. Дерево было немного странное, у каждой вершины дерева было написано значение. Обозначим значение у i-й вершины переменной vi. Теперь Фурукава Нагиса и Оказаки Томоя хотят сыграть в игру с деревом.
Пусть (s, e) — путь из вершины s к вершине e дерева, тогда можно записать последовательность значений вершин на пути (s, e) и обозначить эту последовательность как S(s, e). Определим функцию G от последовательности S(s, e) следующим образом. Предположим, что последовательность равна z0, z1...zl - 1, где l — длина последовательности. Определим G(S(s, e)) = z0 × k0 + z1 × k1 + ... + zl - 1 × kl - 1. Если путь (s, e) удовлетворяет 
, тогда путь (s, e) принадлежит Фурукава Нагисе, в противном случае он принадлежит Оказаки Томоя.
Считать, у кого больше путей, слишком легко, поэтому ребята хотят поиграть во что-то посложнее. Фурукава Нагиса выдвинула гипотезу:
- если пути (p1, p2) и (p2, p3) принадлежат ей, то и путь (p1, p3) тоже принадлежит ей;
- если пути (p1, p2) и (p2, p3) принадлежат Оказаки Томоя, то и путь (p1, p3) тоже принадлежит Оказаки Томоя.
Конечно, описанное выполняется не для всех троек (p1, p2, p3). Итак, теперь Фурукава Нагиса хочет узнать, сколько троек (p1, p2, p3) удовлетворяют ее условию — и это ваша задача.
В первой строке записано четыре целых числа n, y, k и x (1 ≤ n ≤ 105; 2 ≤ y ≤ 109; 1 ≤ k < y; 0 ≤ x < y), здесь n является количеством вершин дерева. Гарантируется, что y является простым числом.
Во второй строке записано n целых чисел: v1, v2, ..., vn (0 ≤ vi < y).
Затем следуют n - 1 строк, в каждой строке записано по два целых числа, обозначающих ребро дерева. Вершины дерева пронумерованы от 1 до n.
Выведите единственное целое число — количество троек, удовлетворяющих гипотезе Фурукава Нагисы.
1 2 1 0
1
1
3 5 2 1
4 3 1
1 2
2 3
14
8 13 8 12
0 12 7 4 12 0 8 12
1 8
8 4
4 6
6 2
2 3
8 5
2 7
341
