Digit Tree

题意翻译

给定一棵树，边权 $1 \leq w\leq 9$。给定一个数 $M$，保证 $\gcd(M,10)=1$。 对于一对有序的不同的顶点 $(u, v)$，他沿着从顶点 $u$ 到顶点 $v$ 的最短路径，按经过顺序写下他在路径上遇到的所有数字（从左往右写），如果得到一个可以被 $M$ 整除的十进制整数，那么就认为 $(u,v)$ 是有趣的点对。 求有趣的对的数量。 $n\leq 10^5$，$m\leq 10^9$。

题目描述

ZS the Coder has a large tree. It can be represented as an undirected connected graph of $ n $ vertices numbered from $ 0 $ to $ n-1 $ and $ n-1 $ edges between them. There is a single nonzero digit written on each edge. One day, ZS the Coder was bored and decided to investigate some properties of the tree. He chose a positive integer $ M $ , which is coprime to $ 10 $ , i.e. . ZS consider an ordered pair of distinct vertices $ (u,v) $ interesting when if he would follow the shortest path from vertex $ u $ to vertex $ v $ and write down all the digits he encounters on his path in the same order, he will get a decimal representaion of an integer divisible by $ M $ . Formally, ZS consider an ordered pair of distinct vertices $ (u,v) $ interesting if the following states true: - Let $ a_{1}=u,a_{2},...,a_{k}=v $ be the sequence of vertices on the shortest path from $ u $ to $ v $ in the order of encountering them; - Let $ d_{i} $ ( $ 1<=i&lt;k $ ) be the digit written on the edge between vertices $ a_{i} $ and $ a_{i+1} $ ; - The integer  is divisible by $ M $ . Help ZS the Coder find the number of interesting pairs!

输入输出格式

输入格式

The first line of the input contains two integers, $ n $ and $ M $ ( $ 2<=n<=100000 $ , $ 1<=M<=10^{9} $ , ) — the number of vertices and the number ZS has chosen respectively. The next $ n-1 $ lines contain three integers each. $ i $ -th of them contains $ u_{i},v_{i} $ and $ w_{i} $ , denoting an edge between vertices $ u_{i} $ and $ v_{i} $ with digit $ w_{i} $ written on it ( $ 0<=u_{i},v_{i}&lt;n,1<=w_{i}<=9 $ ).

输出格式

Print a single integer — the number of interesting (by ZS the Coder's consideration) pairs.

输入输出样例

输入样例 #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

说明

In the first sample case, the interesting pairs are $ (0,4),(1,2),(1,5),(3,2),(2,5),(5,2),(3,5) $ . The numbers that are formed by these pairs are $ 14,21,217,91,7,7,917 $ respectively, which are all multiples of $ 7 $ . Note that $ (2,5) $ and $ (5,2) $ are considered different. In the second sample case, the interesting pairs are $ (4,0),(0,4),(3,2),(2,3),(0,1),(1,0),(4,1),(1,4) $ , and $ 6 $ of these pairs give the number $ 33 $ while $ 2 $ of them give the number $ 3333 $ , which are all multiples of $ 11 $ .