← 返回题目列表

Codeforces · 715/C

C. 数字树

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

ZS 编码器有一棵大树。它可以表示为由编号为 0 到 n - 1 的 n 个顶点以及它们之间的 n - 1 条边组成的无向连通图。每个边缘上都写有一个非零数字。

有一天,编码员 ZS 很无聊,决定调查一下这棵树的一些属性。他选择了一个与 10 互质的正整数 M,即 $$\gcd(M, 10) = 1$$。

ZS 认为一对有序的不同顶点 (u, v) 很有趣,如果他沿着从顶点 u 到顶点 v 的最短路径并以相同的顺序写下他在路径上遇到的所有数字,他将得到可被 M 整除的整数的十进制表示。

形式上,如果满足以下条件,则 ZS 认为一对有序的不同顶点 (u, v) 是有趣的:

- 设 a1 = u, a2, ..., ak = v 为从 u 到 v 的最短路径上的顶点序列(按照遇到它们的顺序);
- 令 di (1 ≤ i < k) 为写在顶点 ai 和 ai + 1 之间的边上的数字;
- 整数 $$\frac{d_1 d_2 \ldots d_{k-1}}{d_k} = \sum_{i=1}^{k-1} d_i \cdot 10^{k-1-i}$$ 可以被 M 整除。

帮助编码员 ZS 找到有趣对的数量!

输入

输入的第一行包含两个整数,n 和 M (2 ≤ n ≤ 100 000, 1 ≤ M ≤ 109, $$\gcd(M, 10) = 1$$) - 分别是顶点数和 ZS 选择的数。

接下来的 n - 1 行每行包含三个整数。其中第 i 个包含 ui、vi 和 wi,表示顶点 ui 和 vi 之间的一条边,上面写有数字 wi(0 ≤ ui,vi < n,1 ≤ wi ≤ 9)。

输出

打印一个整数——有趣的(由 ZS 编码员考虑)对的数量。

示例

输入 #1

6 7
0 1 2
4 2 4
2 0 1
3 0 9
2 5 7

输出 #1

7

输入 #2

5 11
1 2 3
2 0 3
3 0 3
4 3 3

输出 #2

8

注意

在第一个示例案例中,有趣的对是 (0, 4)、(1, 2)、(1, 5)、(3, 2)、(2, 5)、(5, 2)、(3, 5)。这些对组成的数字分别是 14、21、217、91、7、7、917,它们都是 7 的倍数。请注意,(2, 5) 和 (5, 2) 被认为是不同的。

在第二个示例案例中,有趣的对是 (4, 0)、(0, 4)、(3, 2)、(2, 3)、(0, 1)、(1, 0)、(4, 1)、(1, 4),其中 6 个对给出数字 33,其中 2 个对给出数字 3333,它们都是 11 的倍数。