Digit Tree

· · 个人记录

题目

给定一棵树与数P，保证gcd(P,10)=1。树的边权为1−9的数字。

定义dis(u,v)：将从u走到v经过的边上的数字依次以字符串的方式连接成的数。

如：U—4—W—8—S—3—V，dis(U,V)=483。

求满足dis(u,v)是P倍数的(u,v)对数。

题解

判断整除，我们可以直接在mod (P) 的情况下进行计算，看一看最后是不是0。注意到gcd(P,10)=1,意味着我们可以求10在mod(P)情况下的逆元

我们记一个节点向上到根节点所能产生的数为up[u],从根节点向下所能产生的数为down[u]，设v为u的子节点，那么显然：

up[v]=up[u]*10+val[i] down[v]=val[i]*10^{dep[u]}+down[u]

同样，记Up(u,v)为u向上到v所能产生的数，Down(u,v)为从u向下到v所能产生的数，有:

Up(u,v)=(up[u]-up[v])*10^{-dep[v]} Down(u,v)=dep[v]-down[u]*10^{dep[v]-dep[u]}

我们可以枚举LCA，设LCA为x，设端点分别为u,v

那么只有在:

Up(u,x)*10^{dep[v]-dep[x]}+Down(x,v)\equiv0(modP)

的情况下u，v符合要求。

代入移项整理就是：

up[u]=up[x]-down[v]*10^{2dep[x]-dep[v]}+down[x]*10^{dep[x]} down[v]*10^{-dep[v]}=(up[x]-up[u])*10^{-2dep[x]}+down[x]*10^{-dep[x]}

注意到等式的左边已经只与up[u],down[v]*10^{-dep[v]}有关了

于是我们就可以用两个map分别来保存不同up[u],down[v]*10^{-dep[v]}出现的个数，然后使用DSU将子树的信息向上收集。

每次将当前节点作为LCA，枚举轻儿子，将重儿子的信息在map中保留下来。solve的同时计算等式右边的内容，在map中查询有多少个左边与其相等并累加即可复杂度为O(nlog_2^2(n))

在确定LCA枚举u时，当前u的子树中,是不能存在于map中的，故添加与计算要分开进行，先计算一棵子树，再将其添加进map中

注意一些事情,如down[v]*10^{-dep[v]}这样的表达式在计算的时候会显得不对劲，但由于开始整理前都是整数，直接乘逆元的时候不会出什么事情，可以放心大胆的用