CF715C Digit Tree

ZS the Coder 有一棵大树。它可以表示为一个有 $n$ 个顶点（编号从 $0$ 到 $n-1$）、$n-1$ 条边且无向连通的图。每条边上都写有一个非零数字。 有一天，ZS the Coder 感到无聊，决定研究树的一些性质。他选择了一个与 $10$ 互质的正整数 $M$。 ZS 认为有序的不同顶点对 $(u,v)$ 是有趣的，当且仅当从顶点 $u$ 到顶点 $v$ 的最短路径上依次写下路径经过的所有边上的数字，从而组成的整数能够被 $M$ 整除。 形式化来说，ZS 认为有序的不同顶点对 $(u,v)$ 是有趣的，当且仅当以下条件成立： - 设 $a_{1}=u,a_{2},...,a_{k}=v$ 是从 $u$ 到 $v$ 的最短路径上经过的顶点序列； - 设 $d_{i}$（$1\leq i

第一行包含两个整数 $n$ 和 $M$（$2\leq n\leq 100000$，$1\leq M\leq 10^{9}$，$\gcd(M,10)=1$）——顶点数和 ZS 选择的整数 $M$。 接下来 $n-1$ 行每行包含三个整数：$u_{i}, v_{i}, w_{i}$，表示在顶点 $u_i$ 和 $v_i$ 之间有一条边，边上写有数字 $w_i$（$0\leq u_{i},v_{i}

输出一个整数，表示有趣的有序顶点对的数量。

在第一个样例中，有趣的有序对为 $(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$ 整除。 由 ChatGPT 5 翻译