题意：一棵树，边上有一个个位数字，走一条路径会得到一个数字，求有多少路径得到的数字可以整除$P$

路径统计一般就是点分治了

经过一个点的路径，统计出从根走到一个点的数字\(b\)，和从点走到根的数字\(a\)，然后a排序枚举b二分查找范围就行了

然后再减去同一颗子树的

这样可以避免使用平衡树

Candy?这个沙茶一开始ab搞反了

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

typedef long long ll;

#define pii pair<ll, ll>

#define MP make_pair

#define fir first

#define sec second

const int N=1e5+5, INF=1e9;

int read(){

    char c=getchar();int x=0,f=1;

    while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}

    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}

    return x*f;

}

int n, P, u, v, w;

struct edge{int v, w, ne;}e[N<<1];

int cnt, h[N];

inline void ins(int u, int v, int w) {

	e[++cnt]=(edge){v, w, h[u]}; h[u]=cnt;

	e[++cnt]=(edge){u, w, h[v]}; h[v]=cnt;

}

int size[N], f[N], root, All, vis[N];

void dfsRt(int u, int fa) {

	size[u]=1; f[u]=0;

	for(int i=h[u];i;i=e[i].ne)

		if(!vis[e[i].v] && e[i].v != fa) {

			dfsRt(e[i].v, u);

			size[u] += size[e[i].v];

			f[u] = max(f[u], size[e[i].v]);

		}

	f[u] = max(f[u], All-size[u]);

	if(f[u] < f[root]) root = u;

}

ll Pow[N];

int deep[N], m;

ll a[N], ans; pii g[N], b[N];

void dfsIfo(int u, int fa) { //printf("dfsIfo %d  %d  %lld %lld\n", u, deep[u], g[u].fir, g[u].sec);

	a[++m] = g[u].sec, b[m] = MP(g[u].fir, deep[u]);

	for(int i=h[u];i;i=e[i].ne)

		if(!vis[e[i].v] && e[i].v != fa) {

			deep[e[i].v] = deep[u]+1;

			g[e[i].v] = MP( (g[u].fir * 10 + e[i].w)%P, (e[i].w * Pow[deep[u]] + g[u].sec)%P );

			dfsIfo(e[i].v, u);

		}

}

void exgcd(int a, int b, int &d, int &x, int &y) {

	if(b==0) d=a, x=1, y=0;

	else exgcd(b, a%b, d, y, x), y -= (a/b)*x;

}

ll inv(int a, int b) {

	int d, x, y;

	exgcd(a, b, d, x, y);

	return d==1 ? (x+b)%b : -1;

}

void cal(int u, int val) { //printf("\ncal %d %d  %lld\n",u, val, ans);

	sort(a+1, a+1+m); //for(int i=1; i<=m; i++) printf("%lld ",a[i]);puts("");

	for(int i=1; i<=m; i++) {

		ll x = b[i].fir, d = b[i].sec;

		ll v = (P - x) * inv(Pow[d], P) % P;

		int l = lower_bound(a+1, a+1+m, v) - a, r = upper_bound(a+1, a+1+m, v) - a;

		//printf("vvv %lld %d   %d  %d %d\n",x, d, v,l,r);

		ans += (r-l)*val;

	}

	//printf("ans %d\n\n",ans);

}

void dfsSol(int u) { //printf("\nDDDDDDDDDDDDDDDdfsSol %d\n",u);

	vis[u]=1;

	deep[u]=0; g[u].fir = g[u].sec = 0;

	m=0; dfsIfo(u, 0); cal(u, 1);

	for(int i=h[u];i;i=e[i].ne)

		if(!vis[e[i].v]) {

			int v = e[i].v;

			deep[v]=1; g[v].fir = g[v].sec = e[i].w;

			m=0; dfsIfo(v, 0); cal(v, -1);

			All = size[v]; root=0; dfsRt(v, 0); //printf("hiroot %d  %d\n",v,root);

			dfsSol(root);

		}

}

int main() {

	//freopen("in","r",stdin);

	n=read(); P=read(); Pow[0]=1;

	for(int i=1; i<n; i++) u=read()+1, v=read()+1, ins(u, v, read()%P), Pow[i] = Pow[i-1]*10%P;

	All=n; root=0; f[0]=INF;

	dfsRt(1, 0); //printf("root %d\n",root);

	dfsSol(root);

	//printf("%lld",ans-n);

	cout << ans-n;

}