CF434E Furukawa Nagisa's Tree

有一天冈崎朋也和送给古河渚一棵树作为渚的生日礼物。（因为渚的生日是 12.24 啊~）。这是一棵奇奇怪怪的树，每一个节点都有一个权值 $v_i$。现在渚和朋也想在这棵树上玩一个游戏。 设 $ (s,e) $ 为从节点 $s$ 到节点 $e$ 的路径，我们可以写下路径 $ (s,e) $ 上的节点值序列，并将此序列表示为 $ S(s,e) $。 可爱的渚这样定义了一个序列的权值： $G(S(s,e)) $。假设这个序列是 $ z_{0},z_{1}...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} $。 如果这条序列满足 $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}) $ 满足她的结论，这就是你的任务啦！ 翻译者：永远喜欢 Furukawa Nagisa 的 zcysky。

有一天，冈崎朋也买了一棵树作为古河渚的生日礼物。这棵树非常奇怪，每个节点都有一个值。第 $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 翻译