CF716E Digit Tree 点分治

题意：

　　给出一个树，每条边上写了一个数字，给出一个P，求有多少条路径按顺序读出的数字可以被P整除。保证P与10互质。

分析：

　　统计满足限制的路径，我们首先就想到了点分治。

　　随后我们就需要考量，我们是否能统计过某个点的合法路径。我们看，由题目性质，我们可以求对于一个根，所有点到根的路径组成的数，以及根到所有点的路径所组成的数。然后我们就可以对前者开一个数组（其实是一个map容器），后者在上面查询，然后用点分治的去重套路，保证答案不重不漏。

代码：

 #include<bits/stdc++.h>

 #define int long long

 using namespace std;

 const int N=,inf=0x3f3f3f3f;

 struct node{int y,z,nxt;}e[N*];int ans;

 int sm,h[N],c=,vis[N],d[N],siz[N],mx[N];

 int rt,n,m,pw[N],tot,dis[N];map<int,int>mp;

 void add(int x,int y,int z){

     e[++c]=(node){y,z,h[x]};h[x]=c;

     e[++c]=(node){x,z,h[y]};h[y]=c;

 } void getrt(int x,int fa){

     siz[x]=;mx[x]=;

     for(int i=h[x],y;i;i=e[i].nxt)

     if((y=e[i].y)!=fa&&!vis[y]){

         getrt(y,x);siz[x]+=siz[y];

         mx[x]=max(mx[x],siz[y]);

     } mx[x]=max(mx[x],sm-siz[x]);

     if(mx[x]<mx[rt]) rt=x;return ;

 } void exgcd(int a,int b,int &d,int &x,int &y){

     if(!b) d=a,x=,y=;

     else exgcd(b,a%b,d,y,x),y-=x*(a/b);

 } int inv(int a,int p){

     int x,y,d;exgcd(a,p,d,x,y);

     return d==?(x%p+p)%p:-;

 } void dfs(int x,int fa,int v1,int v2,int dep){

     if(dep){

         mp[v2%m]++;dis[++tot]=v1;d[tot]=dep;

     } for(int i=h[x],y;i;i=e[i].nxt)

     if((y=e[i].y)!=fa&&!vis[y]){

         dfs(y,x,(v1*%m+e[i].z)%m,

         (v2+e[i].z*pw[dep]%m)%m,dep+);

     } return ;

 } int calc(int x,int v,int op){

     int res=;tot=;mp.clear();

     dfs(x,,v,v,op);

     for(int i=;i<=tot;i++){

         int val=(m-dis[i]*inv(pw[d[i]],m)%m)%m;

         if(mp.find(val)!=mp.end()) res+=mp[val];

         if(!op) res+=(dis[i]==);

     } if(!op) res+=mp[];return res;

 } void solve(int x){

     ans+=calc(x,,);vis[x]=;

     for(int i=h[x],y;i;i=e[i].nxt)

     if(!vis[y=e[i].y]){

         ans-=calc(y,e[i].z,);

         mx[rt=]=inf;sm=siz[y];

         getrt(y,);solve(rt);

     } return ;

 } signed main(){

     scanf("%lld%lld",&n,&m);

     for(int i=,x,y,z;i<n;i++)

     scanf("%lld%lld%lld",&x,&y,&z),

     add(x+,y+,z);

     pw[]=;for(int i=;i<=n;i++)

     pw[i]=1ll*pw[i-]*%m;

     mx[rt=]=inf;sm=n;

     getrt(,);solve(rt);

     printf("%lld\n",ans);

     return ;

 }

点分治

巴特西

CF716E Digit Tree 点分治

题意：

分析：

最新文章

热门文章