fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1<<17;
  6. const int LOG = 18;
  7.  
  8. vector < int > v[N],digit[N];
  9.  
  10. namespace cd {
  11.     int sz[N];
  12.     bool used[N];
  13.     int parent[N];
  14.     int link[N];
  15.     #define cd_parent parent
  16.     void cd_dfs(int node, vector < int > &path) {
  17.         used[node]=true;
  18.         path.push_back(node);
  19.         sz[node]=1;
  20.         int i;
  21.         for(i=0;i<(int)(v[node].size());i++) if(!used[v[node][i]]) {
  22.             cd_dfs(v[node][i],path);
  23.             sz[node]+=sz[v[node][i]];
  24.         }
  25.     }
  26.  
  27.     int get_centroid(int node, int cnt) {
  28.         int i,max_size=-1,who;
  29.         used[node]=true;
  30.         for(i=0;i<(int)(v[node].size());i++) if(!used[v[node][i]]) {
  31.             if(sz[v[node][i]]>max_size) max_size=sz[v[node][i]],who=v[node][i];
  32.         }
  33.         if(max_size<=(cnt>>1)) return node;
  34.         else return get_centroid(who,cnt);
  35.     }
  36.  
  37.     int centroid_decomposition(int node) {
  38.         int i,ans;
  39.         vector < int > nodes;
  40.         cd_dfs(node,nodes);
  41.         for(i=0;i<(int)(nodes.size());i++) used[nodes[i]]=false;
  42.         ans=get_centroid(node,(int)(nodes.size()));
  43.         for(i=0;i<(int)(nodes.size());i++) used[nodes[i]]=false;
  44.         used[ans]=true;
  45.         for(i=0;i<(int)(v[ans].size());i++) if(!used[v[ans][i]]) cd_parent[centroid_decomposition(v[ans][i])]=ans;
  46.         return ans;
  47.     }
  48. }
  49.  
  50. #define pow oaighkjqghja
  51. #define pow10 pow
  52.  
  53. int n,m;
  54. int pow[N];
  55. map < int, int > cnt[N];
  56. map < pair < int, int >, int > cnt2[N];
  57. long long ans;
  58. int root;
  59. bool used[N];
  60. int parent[N],level[N];
  61. int link[N];
  62. int jump[N][LOG];
  63. int jump_value[N][LOG];
  64. int partial_reversed_value[N];
  65.  
  66. int fpow(int a, int b) {
  67.     if(a==0) return 0;
  68.     if(b==0) return 1;
  69.     int p=fpow(a,b>>1);
  70.     p=(p*1ll*p)%m;
  71.     if(b&1) p=(p*1ll*a)%m;
  72.     return p;
  73. }
  74.  
  75. int div_mod(int a, int b) {
  76.     return (a*1ll*fpow(b,m-2))%m;
  77. }
  78.  
  79. void dfs(int node) {
  80.     partial_reversed_value[node]=(partial_reversed_value[parent[node]]*1ll*10)%m;
  81.     partial_reversed_value[node]=(partial_reversed_value[node]+link[node])%m;
  82.     used[node]=true;
  83.     int i;
  84.     for(i=0;i<(int)(v[node].size());i++) if(!used[v[node][i]]) parent[v[node][i]]=node,level[v[node][i]]=level[node]+1,link[v[node][i]]=digit[node][i],dfs(v[node][i]);
  85. }
  86.  
  87. int walk_up(int node, int lvl) {
  88.     int i;
  89.     for(i=16;i>=0;i--) if(jump[node][i]>=lvl) node=jump[node][i];
  90.     return node;
  91. }
  92.  
  93. int get_lca(int a, int b) {
  94.     if(level[a]>level[b]) swap(a,b);
  95.     b=walk_up(b,level[a]);
  96.     if(a==b) return a;
  97.     int i;
  98.     for(i=16;i>=0;i--) if(jump[a][i]!=jump[b][i]) a=jump[a][i],b=jump[b][i];
  99.     return parent[a];
  100. }
  101.  
  102. int get_distance(int a, int b) {
  103.     return level[a]+level[b]-(level[get_lca(a,b)]<<1);
  104. }
  105.  
  106. int get_jump_value(int a, int b) {
  107.     int ans=0,i;
  108.     for(i=16;i>=0;i--) {
  109.         if(level[jump[a][i]]>=level[b]) {
  110.             ans=(ans*1ll*pow[1<<i])%m;
  111.             ans=(ans+jump_value[a][i])%m;
  112.             a=jump[a][i];
  113.         }
  114.     }
  115.     return ans;
  116. }
  117.  
  118. int get_reversed_value(int a, int b) {
  119.     int ans=(partial_reversed_value[a]-(pow[level[a]-level[b]]*1ll*partial_reversed_value[b])%m+m)%m;
  120.     //ans=div_mod(ans,pow[level[b]-level[a]]);
  121.     return ans;
  122. }
  123.  
  124. int get_value(int a, int b) {
  125.     int their_lca=get_lca(a,b),dist1=level[a]-level[their_lca],dist2=level[b]-level[their_lca],ans;
  126.     ans=(get_jump_value(a,their_lca)*1ll*pow[dist2])%m;
  127.     ans=(ans+get_reversed_value(b,their_lca))%m;
  128.     return ans;
  129. }
  130.  
  131. void update(int node) {
  132.     int value,from=-1,where=node;
  133.     while(where) {
  134.         value=get_value(node,where);
  135.         ++cnt[where][value];
  136.         ++cnt2[where][make_pair(value,from)];
  137.         from=where;
  138.         where=cd::parent[where];
  139.     }
  140. }
  141.  
  142. int query(int node) {
  143.     int value,ans=0,length,need,from=-1,where=node;
  144.     while(where) {
  145.         value=get_value(where,node);
  146.         need=(0-value+m)%m;
  147.         length=get_distance(where,node);
  148.         need=div_mod(need,pow[length]);
  149.         ans+=cnt[where][need]-cnt2[where][make_pair(need,from)];
  150.         from=where;
  151.         where=cd::parent[where];
  152.     }
  153.     return ans;
  154. }
  155.  
  156. int main() {
  157.     int i,j,x,y,z;
  158.  
  159.     scanf("%d %d", &n, &m);
  160.     pow[0]=1;
  161.     for(i=1;i<N;i++) pow[i]=(pow[i-1]*1ll*10)%m;
  162.     for(i=1;i<n;i++) scanf("%d %d %d", &x, &y, &z),++x,++y,v[x].push_back(y),v[y].push_back(x),digit[x].push_back(z),digit[y].push_back(z);
  163.     level[1]=1;
  164.     dfs(1);
  165.     for(i=1;i<=n;i++) jump[i][0]=parent[i],jump_value[i][0]=link[i];
  166.     for(j=1;j<=16;j++) for(i=1;i<=n;i++) {
  167.         jump[i][j]=jump[jump[i][j-1]][j-1];
  168.         jump_value[i][j]=jump_value[i][j-1];
  169.         jump_value[i][j]=(jump_value[i][j]*1ll*pow[1<<(j-1)])%m;
  170.         jump_value[i][j]=(jump_value[i][j]+jump_value[jump[i][j-1]][j-1])%m;
  171.     }
  172.     root=cd::centroid_decomposition(1);
  173.     for(i=1;i<=n;i++) update(i);
  174.     for(i=1;i<=n;i++) ans+=query(i);
  175.     printf("%lld\n", ans);
  176.  
  177.     return 0;
  178. }
  179.  
Runtime error #stdin #stdout 0s 35480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pP3kPg
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!