题意：
给出一个树，每条边上写了一个数字，给出一个P，求有多少条路径按顺序读出的数字可以被P整除。保证P与10互质。
分析：
统计满足限制的路径，我们首先就想到了点分治。
随后我们就需要考量，我们是否能统计过某个点的合法路径。我们看，由题目性质，我们可以求对于一个根，所有点到根的路径组成的数，以及根到所有点的路径所组成的数。然后我们就可以对前者开一个数组（其实是一个map容器），后者在上面查询，然后用点分治的去重套路，保证答案不重不漏。
代码：
1 #include<bits/stdc++.h> 2 #define int long long 3 using namespace std; 4 const int N=100005,inf=0x3f3f3f3f; 5 struct node{int y,z,nxt;}e[N*2];int ans; 6 int sm,h[N],c=1,vis[N],d[N],siz[N],mx[N]; 7 int rt,n,m,pw[N],tot,dis[N];map<int,int>mp; 8 void add(int x,int y,int z){ 9 e[++c]=(node){y,z,h[x]};h[x]=c; 10 e[++c]=(node){x,z,h[y]};h[y]=c; 11 } void getrt(int x,int fa){ 12 siz[x]=1;mx[x]=0; 13 for(int i=h[x],y;i;i=e[i].nxt) 14 if((y=e[i].y)!=fa&&!vis[y]){ 15 getrt(y,x);siz[x]+=siz[y]; 16 mx[x]=max(mx[x],siz[y]); 17 } mx[x]=max(mx[x],sm-siz[x]); 18 if(mx[x]<mx[rt]) rt=x;return ; 19 } void exgcd(int a,int b,int &d,int &x,int &y){ 20 if(!b) d=a,x=1,y=0; 21 else exgcd(b,a%b,d,y,x),y-=x*(a/b); 22 } int inv(int a,int p){ 23 int x,y,d;exgcd(a,p,d,x,y); 24 return d==1?(x%p+p)%p:-1; 25 } void dfs(int x,int fa,int v1,int v2,int dep){ 26 if(dep){ 27 mp[v2%m]++;dis[++tot]=v1;d[tot]=dep; 28 } for(int i=h[x],y;i;i=e[i].nxt) 29 if((y=e[i].y)!=fa&&!vis[y]){ 30 dfs(y,x,(v1*10%m+e[i].z)%m, 31 (v2+e[i].z*pw[dep]%m)%m,dep+1); 32 } return ; 33 } int calc(int x,int v,int op){ 34 int res=0;tot=0;mp.clear(); 35 dfs(x,0,v,v,op); 36 for(int i=1;i<=tot;i++){ 37 int val=(m-dis[i]*inv(pw[d[i]],m)%m)%m; 38 if(mp.find(val)!=mp.end()) res+=mp[val]; 39 if(!op) res+=(dis[i]==0); 40 } if(!op) res+=mp[0];return res; 41 } void solve(int x){ 42 ans+=calc(x,0,0);vis[x]=1; 43 for(int i=h[x],y;i;i=e[i].nxt) 44 if(!vis[y=e[i].y]){ 45 ans-=calc(y,e[i].z,1); 46 mx[rt=0]=inf;sm=siz[y]; 47 getrt(y,0);solve(rt); 48 } return ; 49 } signed main(){ 50 scanf("%lld%lld",&n,&m); 51 for(int i=1,x,y,z;i<n;i++) 52 scanf("%lld%lld%lld",&x,&y,&z), 53 add(x+1,y+1,z); 54 pw[0]=1;for(int i=1;i<=n;i++) 55 pw[i]=1ll*pw[i-1]*10%m; 56 mx[rt=0]=inf;sm=n; 57 getrt(1,0);solve(rt); 58 printf("%lld ",ans); 59 return 0; 60 }