题目描述

给一棵树 n 个顶点，顶点编号为 0 - \(n - 1\)，以及一个数 m，树上的每条边都有一个权值（0 到 9 之间的整数），问有多少点对 (u, v) 使得 u 到 v 路径上的权值组成的数可被 m 整除（像字符串一样组成）。
例如：1 -> 2 : \(w_1\), 2 -> 3 : \(w_2\), …, i-1 -> i : \(w_{i-1}\)；
1 -> i : \(w_1\)\(w_2\)…\(w_{i-1}\) (\(\sum_1^{k-1}w_i \times 10^{k-1-i}\))

输入格式

第一行两个整数 n, m。
接下来 n - 1 行，每行三个整数 \(u_i\), \(v_i\), \(w_i\)，表示 \(u_i\) 到 \(v_i\) 有边权值 \(w_i\) (0 \(\leq\) \(u_i\), \(v_i\) < n)。

输出格式

输出满足条件的点对数。

样例1

输入

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

输出

7

样例2

输入

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

输出

8

数据范围

对于 30%的数据，2 \(\leq\) n \(\leq\) 50, 1 \(\leq\) m \(\leq\) 100, gcd(m, 10) = 1, 0 \(\leq\) \(u_i\), \(v_i\) < n, 1 \(\leq\) \(w_i\) \(\leq\) 9；
对于 100%的数据，2 \(\leq\) n \(\leq\) 100,000, 1 \(\leq\) m \(\leq\) \(10^9\), gcd(m, 10) = 1, 0 \(\leq\) \(u_i\), \(v_i\) < n, 1 \(\leq\) \(w_i\) \(\leq\) 9。

限制

3s, 256M

样例解释

样例 1：点对：(0, 4), (1, 2), (1, 5), (3, 2), (2, 5), (5, 2), (3, 5)，组成的值：
14, 21, 217, 91, 7, 7, 917 ，共 7 对都整除 7。点对(2, 5) 和 (5, 2)是不同
的。

样例 2：点对：(4, 0), (0, 4), (3, 2), (2, 3), (0, 1), (1, 0), (4, 1), (1, 4)，组成
33 和 3333，共8 对都整除11.

来源

Codeforces716E
CWOI新高二专题测试十七