题意：一棵树，边上有一个个位数字，走一条路径会得到一个数字，求有多少路径得到的数字可以整除\(P\)
路径统计一般就是点分治了
\[ a*10^{deep} + b \ \equiv \pmod P\]
\[ a = (P-b)*inv(10^{deep}) \]
经过一个点的路径，统计出从根走到一个点的数字\(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;
}