/ CWOI / 题库 /

2017.07.20 P3 数字树

2017.07.20 P3 数字树

题目描述

给一棵树 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新高二专题测试十七

信息

难度
7
分类
树结构 | 树的分治数论 点击显示
标签
(无)
递交数
1
已通过
1
通过率
100%
上传者