题解 CF715C【Digit Tree】
whiteqwq
·
·
题解
CF715C Digit Tree解题报告：
更好的阅读体验
题意
给定一颗n个点的带边权w_i的树，给定m，求树上有多少条路径从左往右连成的数为m的倍数。（(x,y)与(y,x)为不同的点对）
## 分析
这道题告诉我们，只要肯推式子，很多静态的树上路径计数问题树上启发式合并（dsu on tree）是可以胜任的（如果不会树上启发式合并可以练习一下[CF246E Blood Cousins Return](https://www.luogu.com.cn/problem/CF246E)）。
首先不难发现树上的路径形成的数是高精度也存不下的，因此我们考虑把是$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;
}
```