一句话怎么说来着
算法+高级数据结构=OI
现在我感觉到的是
我会的算法+我会的高级数据结构=WA
这道题提交了三四十次，从刚看题到完全写好花了好几天..，主要死于看错费马小定理的适用条件。
下面是正经题解:
首先，这道题的难点不在于找到有多少个路径（很明显的点分治），而是判断一条路径是否合法。
按照点分治的一般套路。我们可以求出从一个点出发的所有路径，然而把所有路径组合起来就好了。
显然，对于把从$root$到所有子节点的路径的那个数只要不断的乘上去然后$modM$就行了。
所有我们面临的最主要的问题就是如何把两条路径组合起来。
首先，这里指的路径并不是两条完全相同的路径。比如说我们要验证从$node_i$经$root$到$node_j$的路径，我们应该求出$node_i \rightarrow root$数和$root \rightarrow node_j$的数。
不妨设这两个数的为别为$num_i$和$num_j$,把他们的长度（或者说是从根到$node$的深度）即为$deep_i$和$deep_j$，显然，如果$node_i \rightarrow node_j$的路径是合法的，我们可以得到以下关系。
$num_i+num_j \times 10^{deep_j} \equiv 0 (mod M)$
转换一下
$num_i \equiv -num_j \times 10^{-deep_j} (mod M)$
对于这个式子右边的，dfs一遍后用map存储即可。然后累加式子左边的即可。同时，要注意从统计式子右边完后，要-1，具体为什么实现的时候自己就能明白。
同时，$M$不一定为素数，所以这个模的意义一定要用乘法逆元或者欧拉函数什么的求，直接快速幂$M-2$会有问题。
//CF 716E
//by Cydiater
//2016.9.27
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
const int MAXN=1e6+5;
const int oo=0x3f3f3f3f;
inline ll read(){
char ch=getchar();ll x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
map<ll,ll>cnt;
ll N,mod,LINK[MAXN],len=0,pow10[MAXN],inv10[MAXN],root,sum,siz[MAXN],max_siz[MAXN],ans=0,dis[MAXN],deep[MAXN];
struct edge{
ll y,next,v;
}e[MAXN];
bool vis[MAXN];
namespace solution{
inline void insert(ll x,ll y,ll v){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=v;}
inline ll quick_pow(ll a,ll b){
ll tmp=1;
while(b){
if(b&1)tmp=(tmp*a)%mod;
b>>=1;a=(a*a)%mod;
}
return tmp;
}
void make_root(int node,int fa){
siz[node]=1;max_siz[node]=0;
for(int i=LINK[node];i;i=e[i].next)if(!vis[e[i].y]&&e[i].y!=fa){
make_root(e[i].y,node);
siz[node]+=siz[e[i].y];
max_siz[node]=max(max_siz[node],siz[e[i].y]);
}
max_siz[node]=max(max_siz[node],sum-max_siz[node]);
if(max_siz[node]<max_siz[root])root=node;
}
void ex_gcd(ll a,ll b,ll &x,ll &y){
if(b==0){x=1;y=0;return;}
ex_gcd(b,a%b,x,y);
ll t=x;x=y;y=t-a/b*y;
}
ll get_inv(ll num){
ll x,y;
ex_gcd(num,mod,x,y);
return ((x%mod+mod)+mod)%mod;
}
void init(){
N=read();mod=read();
up(i,2,N){
ll x=read()+1,y=read()+1,v=read();
insert(x,y,v);
insert(y,x,v);
}
if(mod<=1){
cout<<N*(N-1)<<endl;
exit(0);
}
pow10[0]=1;
up(i,1,N)pow10[i]=(pow10[i-1]*10)%mod;
up(i,0,N)inv10[i]=get_inv(pow10[i]);//pret
}
void dfs(ll node,ll fa){
ll tmp=(((mod-dis[node])%mod+mod)*inv10[deep[node]]+mod)%mod;
cnt[tmp]++;
for(int i=LINK[node];i;i=e[i].next)if(!vis[e[i].y]&&e[i].y!=fa){
dis[e[i].y]=((dis[node]*10)%mod+e[i].v)%mod;
deep[e[i].y]=deep[node]+1;
dfs(e[i].y,node);
}
}
ll get_ans(int node,int fa){
ll tmp=cnt[dis[node]%mod];
for(int i=LINK[node];i;i=e[i].next)if(!vis[e[i].y]&&e[i].y!=fa){
deep[e[i].y]=deep[node]+1;
dis[e[i].y]=(dis[node]+(e[i].v*pow10[deep[node]])%mod)%mod;
tmp+=get_ans(e[i].y,node);
}
return tmp;
}
ll col(int node,ll dist,int dep){
dis[node]=dist%mod;deep[node]=dep;
dfs(node,0);
cnt[0]--;
return get_ans(node,0);
}
void work(int node){
vis[node]=1;
cnt.clear();
ans+=col(node,0,0);
for(int i=LINK[node];i;i=e[i].next)if(!vis[e[i].y]){
cnt.clear();
ans-=col(e[i].y,e[i].v,1);
root=0;sum=siz[e[i].y];
make_root(e[i].y,0);
work(root);
}
}
void slove(){
root=0;max_siz[root]=oo;sum=N;
make_root(1,0);
work(root);
}
void output(){
cout<<ans<<endl;
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
init();
slove();
output();
}