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

---

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

\[ a*10^{deep} + b \ \equiv \pmod P\]

\[ a = (P-b)*inv(10^{deep}) \]

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

然后再减去同一颗子树的

这样可以避免使用平衡树

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

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long ll;#define pii pair
         
          #define MP make_pair #define fir first#define sec secondconst 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