← 返回题目列表

Codeforces · 434/E

E. 古川渚的树

中文机器翻译题面 查看原题

有一天,冈崎朋也买了一棵树作为古川渚的生日礼物。这棵树很奇怪,树的每个节点都有一个值。第 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) 满足 $$G(S(s,e)) \equiv x (\bmod y)$$,则路径 (s, e) 属于古川渚,否则属于冈崎智也。

计算谁拥有更多的路径太容易了,所以他们想要玩一些更困难的东西。古川渚认为,如果路径(p1,p2)和(p2,p3)属于她,那么路径(p1,p3)也属于她。另外,她认为如果路径(p1,p2)和(p2,p3)属于冈崎智也,那么路径(p1,p3)也属于冈崎智也。但事实上,这个结论并不总是正确的。现在古川渚想知道有多少个三元组 (p1, p2, p3) 的结论是正确的,这就是你的任务。

输入

第一行包含四个整数 n、y、k 和 x(1 ≤ n ≤ 105;2 ≤ y ≤ 109;1 ≤ k < y;0 ≤ x < y) - n 是树上的节点数。保证y是素数。

第二行包含 n 个整数,第 i 个整数是 vi (0 ≤ vi < y)。

然后是n - 1行,每行包含两个整数,表示树的一条边。树的节点编号为 1 到 n。

输出

输出一个整数——古川渚的结论正确的三元组的数量。

示例

输入 #1

1 2 1 0
1

输出 #1

1

输入 #2

3 5 2 1
4 3 1
1 2
2 3

输出 #2

14

输入 #3

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

输出 #3

341