CF434E.Furukawa Nagisa's Tree

有一天，冈崎朋也买了一棵树作为古河渚的生日礼物。这棵树非常奇怪，每个节点都有一个值。第 $i$ 个节点的值为 $v_i$。现在，古河渚和冈崎朋也想在这棵树上玩一个游戏。

设 $(s, e)$ 表示从节点 $s$ 到节点 $e$ 的路径，我们可以记录下该路径上节点的值序列，记作 $S(s, e)$。我们定义该序列的值 $G(S(s, e))$ 如下。假设序列为 $z_0, z_1, \ldots, z_{l-1}$，其中 $l$ 是序列的长度。则有 $G(S(s, e)) = z_0 \times k^{0} + z_1 \times k^{1} + \cdots + z_{l-1} \times k^{l-1}$。如果路径 $(s, e)$ 满足

$$G(S(s, e)) \equiv x \pmod{y}$$

则该路径 $(s, e)$ 属于古河渚，否则属于冈崎朋也。

计算谁拥有更多的路径太简单了，所以他们想玩更难的。古河渚认为如果路径 $(p_1, p_2)$ 和 $(p_2, p_3)$ 都属于她，则路径 $(p_1, p_3)$ 也属于她。同时她还认为，如果路径 $(p_1, p_2)$ 和 $(p_2, p_3)$ 都属于冈崎朋也，则路径 $(p_1, p_3)$ 也属于冈崎朋也。不过实际上，这一结论并不总是正确的。现在古河渚想知道，对于多少个三元组 $(p_1, p_2, p_3)$，她的结论是正确的，这就是你的任务。

第一行包含四个整数 $n$、$y$、$k$ 和 $x$（$1 \leq n \leq 10^5$，$2 \leq y \leq 10^9$，$1 \leq k < y$，$0 \leq x < y$），其中 $n$ 表示树上的节点个数。保证 $y$ 是质数。

第二行包含 $n$ 个整数，第 $i$ 个整数为 $v_i$（$0 \leq v_i < y$）。

接下来 $n-1$ 行，每行包含两个正整数，表示树上的一条边。节点编号为 $1$ 到 $n$。

输出一个整数，表示满足古河渚结论正确的三元组数量。

由 ChatGPT 5 翻译