给定一棵$n$个节点的带边权的无根树和一个与$10$互素的整数$P$，树的边权$\in \lbrace 1,9\rbrace $，问有多少点对$(u,v)$满足从$u$到$v$路径上的边权组成的数字是$P$的倍数。
说正式点，设数列$\lbrace d_n\rbrace $是$u \to v$路径上边权组成的数列，则$u \to v$的边权组成的数字$s=\overline{d_1d_2…d_n}$，即$s=\sum_{i=1}^n 10^{n-i}*d_i$
真的很喜欢这个马来西亚的小哥啊，每次出的div2都是可以AK的。。这场有点可惜，只可以比$50min$，只够口胡一下div2的T5
这个T5一眼树分治套个map
显然可以用树分治来合并所有路径以更新答案。
我们预处理$10$的幂$pw(i)$，在分治的时候用map维护其他节点为开头到重心的路径模$P$得到的值的个数，考虑当前节点作为结尾查询的到重心的链是否可以作为可更新答案的路径的后缀(注意如果当前查询的最为开头的话应该是不可以的因为下面的扩展欧几里得用不了)。
设当前查询到的节点到重心的距离为$d$，重心到它的路径权值在$mod~P$后为$w$
现在我们要计算这条链接在前缀权值$mod\ P$是什么的后面才可以更新答案。不妨设可更新答案的前缀权值为$x$
则可以列出方程: $w+pw[d]\times x \equiv 0 (mod~P)$
傻逼都知道这个扩展欧几里得可以瞎比搞到。
然而一年过去了我还是不会扩欧。。
于是插入一下扩欧是什么玩意:
假设已经求得了 $b x’+(a\%b)y’=gcd(a,b)$的解$x’,y’$
众所周知，$a\%b=a-a/b*b$
则可以得到$b x’ +(a-a/b*b)y’ =gcd(a,b)$
瞎比提项得$ay’ + b(x’-(a/b)y’)=gcd(a,b)$
那么当前式子的解$(x,y)=(y’,x’-(a/b)y’)$
应该已经记下来了这句话说了超过10次了
于是在这题里瞎比展开一下:
$w+pw[d]\times x=Py$
因为题目里已经说过了，$(P,10)=1$，所以这个方程是一定有解的。并且在$mod \ P$的情况下只有$1$解。
所以只要把解出来的$x$无脑乘个$w$再$mod$个$P$即可。
还有一个要提的东西是关于点分治的。
如果题目和路径有关，那么在处理的过程中先到了被删除的重心再return，单独的一条边要提前处理。
而如果信息在节点上，那么被删除的点不用访问。
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<map>
using namespace std;
#define bug(x) cout<<#x<<"="<<x<<" "
#define debug(x) cout<<#x<<"="<<x<<endl
typedef long long ll;
const int INF=(unsigned)-1>>1;
int n,P;
inline void rd(int &a){
a=0;char c;
while(c=getchar(),!isdigit(c));
do a=a*10+(c^48);
while(c=getchar(),isdigit(c));
}
struct Edge{
int to,c,nxt;
}G[(int)2e5+5];
inline int Mod_Pow(int x,int a){
int res=1;
for(;a;a>>=1,x=(ll)x*x%P)
if(a&1)res=(ll)res*x%P;
return res;
}
int head[(int)1e5+5],tot_edge;
inline void add_edge(int from,int to,int c){
G[tot_edge]=(Edge){to,c,head[from]};
head[from]=tot_edge++;
G[tot_edge]=(Edge){from,c,head[to]};
head[to]=tot_edge++;
}
bool mark[(int)1e5+5];
ll res;
inline void Mod_add(int &a,int b){
if((a+=b)>=P)a-=P;
}
map<int,ll>mp;
int sz[(int)1e5+5],pw[(int)1e5+5];
struct node{
int fi,se;
inline bool operator < (const node &tmp)const{
return fi<tmp.fi||fi==tmp.fi&&se<tmp.se;
}
};
inline void Max(int &a,int b){
if(a<b)a=b;
}
inline node find_heart(int v,int f,const int &tot){
node res=(node){INF,0};
int w=0;
for(int i=head[v];~i;i=G[i].nxt){
int to=G[i].to;
if(to==f||mark[to])continue;
node tmp=find_heart(to,v,tot);
if(tmp<res)res=tmp;
Max(w,sz[to]);
}
Max(w,tot-sz[v]+1);
if(w<res.fi)res=(node){w,v};
return res;
}
inline int gcd(int x,int y){
return y?gcd(y,x%y):x;
}
inline void ext_gcd(int a,int b,int &x,int &y){
if(b)ext_gcd(b,a%b,y,x),y-=a/b*x;
else x=1,y=0;
}
inline void predfs(int v,int f){
sz[v]=1;
for(int i=head[v];~i;i=G[i].nxt){
int to=G[i].to;
if(to==f||mark[to])continue;
predfs(to,v);
sz[v]+=sz[to];
}
}
int _x,_y;
inline int Mod(int x){
if(x<0)return x+P;
return x;
}
inline int calc(int w,int a,int b=P){
ext_gcd(a,b,_x,_y);
return (ll)Mod(_x%P)*w%P;
}
inline void dfs(int v,int f,int num,int d){
int k=calc(P-num,pw[d]);
if(mp.find(k)!=mp.end())res+=mp[k];
if(mark[v])return;
for(int i=head[v];~i;i=G[i].nxt){
int to=G[i].to;
if(to==f)continue;
dfs(to,v,((ll)num*10+G[i].c)%P,d+1);
}
}
inline void update(int v,int f,int num,int d=1){
++mp[num];
if(mark[v])return;
for(int i=head[v];~i;i=G[i].nxt){
int to=G[i].to;
if(to==f)continue;
update(to,v,(num+(ll)pw[d]*G[i].c)%P,d+1);
}
}
int s[(int)1e5+5],c[(int)1e5+5];
inline void solve(int v){
predfs(v,v);
int w=find_heart(v,v,sz[v]).se,tp=0;
mark[w]=1;
mp.clear();
for(int i=head[w];~i;i=G[i].nxt){
int to=G[i].to;
s[++tp]=to,c[tp]=G[i].c;
dfs(to,w,G[i].c,1);
update(to,w,G[i].c);
}
mp.clear();
for(int i=tp;i>0;--i){
dfs(s[i],w,c[i],1);
update(s[i],w,c[i]);
}
for(int i=head[w];~i;i=G[i].nxt){
int to=G[i].to;
if(!mark[to])solve(to);
}
mark[w]=1;
}
inline void Init(){
pw[0]=P==1?0:1;
for(int i=1;i<=(int)1e5;++i)
pw[i]=(ll)pw[i-1]*10%P;
}
int main(){
cin>>n>>P;
Init();
memset(head,-1,sizeof(head));
tot_edge=0;
for(int i=1,a,b,c;i<n;++i){
rd(a),rd(b),rd(c),c%=P;
add_edge(a,b,c);
res+=!c<<1;
}
solve(0);
cout<<res<<endl;
return 0;
}