CF715C Digit Tree解题报告

解题报告

---

CF715C Digit Tree解题报告：

更好的阅读体验

题意

给定一颗$n$个点的带边权$w_i$的树，给定$m$，求树上有多少条路径从左往右连成的数为$m$的倍数。（$(x,y)$与$(y,x)$为不同的点对）

$1\leqslant n\leqslant 10^5,1\leqslant m,w_i\leqslant 10^9,\gcd(10,m)=1$。

分析

这道题告诉我们，只要肯推式子，很多静态的树上路径计数问题树上启发式合并（dsu on tree）是可以胜任的（如果不会树上启发式合并可以练习一下CF246E Blood Cousins Return）。

首先不难发现树上的路径形成的数是高精度也存不下的，因此我们考虑把是$m$的倍数转化为对$m$取模，那么我们就只需要在$m$的同余系下运算了。

很容易预处理出来$dis1_x$表示$1$到$x$路径的值，$dis2_x$表示$x$到$1$路径的值，$dep_x$表示$x$的深度（根节点深度为$1$）。

那么我们也可以很方便的计算出来$x$到$y$路径上的值（设$z=\text{lca}(x,y)$）：

$$val(x,y)=\frac{dis2_x-dis2_z}{10^{dep_z}}\times 10^{dep_y-dep_z}+dis1_y-dis1_z\times 10^{dep_y-dep_z}$$

题目要求的就是$val(x,y)$的$(x,y)$对数，看到静态树上路径计数，我们可以考虑用树上启发式合并进行计算：

树上启发式合并具体步骤：对于节点$x$，先计算所有轻儿子的贡献（统计贡献用全局的桶），每统计完一个轻儿子暴力消除贡献，之后统计重儿子的贡献（不清空桶），最后再把轻儿子的贡献加上并计算路径的$\text{lca}$为$x$的贡献。
如果删除和添加节点贡献复杂度为$O(1)$，那么树上启发式合并的复杂度为$O(n\log n)$。

不难发现添加节点的时候仅知道路径的一端，所以我们可以对上面的$val(x,y)\equiv 0\pmod m$的式子进行变形（上面的式子代表$x$是左端点，下面的式子代表$x$是右端点）：

$$dis2_x\equiv dis2_z-\frac{dis1_y\times 10^{2dep_z}}{10^{dep_y}}+dis1_z\times 10^{dep_z}\pmod m$$

$$\frac{dis1_y}{10^{dep_y}}\equiv \frac{dis1_z}{ 10^{dep_z}}-\frac{dis2_x-dis2_z}{10^{2dep_z}}\pmod m$$

那么我们就直接用$\text{map}$存一下左边的值，然后讨论一下就好了（注意这里$\text{map}$不能存右边的值的原因是$dep_z$在重儿子遍历完的时候改变）。

代码

两个要注意的地方：节点编号从$0$开始；$m$不是质数，需要用扩展欧几里得求逆元。

dsu要注意实现的细节

#include<stdio.h>
#include<map>
using namespace std;
const int maxn=100005,maxm=maxn<<1;
int n,m,e,dfns,inv10;
long long ans;
int start[maxn],to[maxm],then[maxm],worth[maxm],size[maxn],iptson[maxn],L[maxn],R[maxn],id[maxn],pow10[maxn<<1],powinv[maxn<<1],dep[maxn],dis1[maxn],dis2[maxn];//dis1[x]:1->x dis2[x]:x->1
map<int,int>mapx,mapy;
inline void add(int x,int y,int z){
    then[++e]=start[x],start[x]=e,to[e]=y,worth[e]=z;
}
int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    int res=exgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return res;
}
int getinv(int a,int mod){
    int x,y;
    exgcd(a,mod,x,y);
    return (x%mod+mod)%mod;
}
void dfs1(int x,int last){
    L[x]=++dfns,id[dfns]=x,size[x]=1,iptson[x]=-1,dep[x]=dep[last]+1;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        dis1[y]=(10ll*dis1[x]%m+worth[i])%m,dis2[y]=(dis2[x]+1ll*pow10[dep[x]]*worth[i]%m)%m;
        dfs1(y,x),size[x]+=size[y];
        if(iptson[x]==-1||size[iptson[x]]<size[y])
            iptson[x]=y;
    }
    R[x]=dfns;
}
inline void calc(int x,int z){
    ans+=mapx[(dis2[z]-1ll*dis1[x]*pow10[dep[z]*2]%m*powinv[dep[x]]%m+1ll*dis1[z]*pow10[dep[z]]%m+m)%m];
    ans+=mapy[(1ll*dis1[z]*powinv[dep[z]]%m-1ll*(dis2[x]-dis2[z]+m)%m*powinv[dep[z]*2]%m+m)%m];
}
void dfs2(int x,int last){
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last||y==iptson[x])
            continue;
        dfs2(y,x),mapx.clear(),mapy.clear();
    }
    if(iptson[x]!=-1)
        dfs2(iptson[x],x);
    calc(x,x);
    mapx[dis2[x]]++,mapy[1ll*dis1[x]*powinv[dep[x]]%m]++;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last||y==iptson[x])
            continue;
        for(int j=L[y];j<=R[y];j++)
            calc(id[j],x);
        for(int j=L[y];j<=R[y];j++)
            mapx[dis2[id[j]]]++,mapy[1ll*dis1[id[j]]*powinv[dep[id[j]]]%m]++;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    if(m==1){
        printf("%lld\n",1ll*n*(n-1));
        return 0;
    }
    inv10=getinv(10,m),pow10[0]=powinv[0]=1;
    for(int i=1;i<=n*2;i++)
        pow10[i]=pow10[i-1]*10ll%m,powinv[i]=1ll*powinv[i-1]*inv10%m;
    for(int i=1;i<n;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        x++,y++,add(x,y,z),add(y,x,z);
    }
    dfs1(1,0),dfs2(1,0);
    printf("%lld\n",ans);
    return 0;
}