fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define int long long
  5. using namespace std;
  6. const long long oo=1e18;
  7. int mod=1e9+7;
  8. int Test=1;
  9. void home()
  10. {
  11.     if(fopen("main.inp","r")) 
  12.     freopen("main.inp","r",stdin),
  13.     freopen("main.out","w",stdout);
  14. }
  15. bool bit(int x,int i){return (x>>i)&1;}
  16. int n;
  17. vector<pair<int,int>>a[100005];
  18. int Phi,sz[100005],del[100005],mu[100005],inv[100005];
  19. int PhiHam(int n) 
  20. {
  21.     int res=n;
  22.     for(int i=2;i*i<=n;i++) 
  23.     {
  24.         if(n%i==0) 
  25.         {
  26.             while(n%i==0) 
  27.                 n/=i;
  28.             res-=res/i;
  29.         }
  30.     }
  31.     if(n!=1)res-=res/n;
  32.     return res;
  33. }
  34. int Pow(int a,int b)
  35. {
  36.     int res=1;
  37.     for(;b;b>>=1)
  38.     {
  39.         if(b&1)res=(res*a)%mod;
  40.         a=(a*a)%mod;
  41.     }
  42.     return res;
  43. }
  44. int NghichDao(int n)
  45. {
  46.     return Pow(n,Phi-1);
  47. }
  48. int Rev(int u) 
  49. {
  50.     u=((u*-1)%mod+mod)%mod;
  51.     return u;
  52. }
  53. void CalSz(int u,int par)
  54. {
  55.     sz[u]=1;
  56.     for(auto [v,w]:a[u])
  57.         if(v!=par&&!del[v])CalSz(v,u),sz[u]+=sz[v];
  58. }
  59. int Centroid(int u,int par,int n)
  60. {
  61.     for(auto [v,w]:a[u])
  62.     {
  63.         if(v!=par&&!del[v]&&sz[v]>n/2)
  64.             return Centroid(v,u,n);
  65.     }
  66.     return u;
  67. }
  68. int kq=0;
  69. map<int,int>len,xuong;
  70. void DFS(int u,int par,int pha,int DiXuong,int DiLen,int sau)
  71. {
  72.     if(!pha)
  73.     {
  74.         kq+=len[Rev(DiXuong)*inv[sau]%mod];
  75.         kq+=xuong[DiLen];
  76.     } 
  77.     else
  78.     {
  79.         len[DiLen]++;
  80.         xuong[Rev(DiXuong)*inv[sau]%mod]++;
  81.     }
  82.     for(auto [v,w]:a[u])if(v!=par&&!del[v])DFS(v,u,pha,(DiXuong*10+w)%mod,(w*mu[sau]+DiLen)%mod,sau+1);
  83. }
  84. void Decompose(int u)
  85. {
  86.     CalSz(u,0);
  87.     u=Centroid(u,0,sz[u]);
  88.     len[0]=xuong[0]=1;
  89.     for(auto [v,w]:a[u])
  90.     {
  91.         if(!del[v])
  92.         {
  93.             DFS(v,u,0,w,w,1);
  94.             DFS(v,u,1,w,w,1);
  95.         }
  96.     }
  97.     del[u]=1;
  98.     len.clear();xuong.clear();
  99.     for(auto [v,w]:a[u])if(!del[v])Decompose(v);
  100. }
  101. void Tcmduc_VOI26()
  102. {
  103.     cin>>n>>mod;mu[0]=1;Phi=PhiHam(mod);
  104.     inv[0]=NghichDao(1);
  105.     for(int i=1;i<=n;i++)
  106.     {
  107.         mu[i]=(mu[i-1]*10)%mod;
  108.         inv[i]=NghichDao(mu[i]);
  109.     }
  110.     for(int i=1;i<n;i++)
  111.     {
  112.         int u,v,w;cin>>u>>v>>w;u++,v++;w%=mod;
  113.         a[u].push_back({v,w});
  114.         a[v].push_back({u,w});
  115.     }
  116.     Decompose(1);
  117.     cout<<kq;
  118. }
  119. signed main()
  120. {
  121.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);home();
  122.     while(Test--)Tcmduc_VOI26();
  123.     cerr<<'\n';
  124.     return 0;
  125. }
  126.  
Success #stdin #stdout #stderr 0.01s 8992KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 

    

	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/dhP0sC
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
7 days ago

					

					

						
visibility:

						

							 public																												
							
							

								
							

						

					

										
										

					
					 Share or Embed source code
					
					
					
					

						
						
						
						
						
						
						
					

					
						
	
	
	
	
					
					
					
					
					 
					
					
					
					 
					
					
					
					
					
					

					

					

					
						
					

					


	
Discover > Sphere Engine API

	
The brand new service which powers Ideone!

	
	
Discover > IDE Widget

    
Widget for compiling and running the source code in a web browser!