D

给一张无向图,有一些边权值不确定
现在要求将这些边权值确定,使得s-t的最短路为L
要求权值在[1,1e18]

二分 最短路

对于不确定的边二分一个p,前p个赋为1,剩下的赋为INF
若二分到一个p,恰好w[p]=1时,最短路<=L,w[p]=INF,最短路>L
则说明第p条路径为一个关键路径,其会影响最短路的长度
将其权值改为1 + L - |最短路|

E

树的每条边上有一个数位(1-9)
统计有多少条链,使得其表示的十进制数可以被M整除
(不同方向统计两次)

树分治

我们dfs所有从根出发%m的值
按顺序记为 d1[v],逆序记为 d2[v]

$d2_u \times 10^{dep_v}+ d1_v \equiv 0\ mod\ m$

$d2_u \equiv -d1_v \times \frac{1}{10^{dep_v}}\ mod\ m$

可以预处理出所有$10^n$的逆元,先dfs d1,然后dfs d2顺便统计
注意若
$d2_v = -d1_v \times \frac{1}{10^{dep_v}}\ mod\ m$

则说明这条链正向与反向构成了一个合法答案,应该去掉

复杂度 $O(nlog^2n)$