YBTOJ&洛谷P3292：幸运数字（线性基、点分治/倍增）

解析
虽然使用三个log的倍增算法艹过去了 但是我们还是来聊聊正解吧
考虑点分治 对于当前的根，dfs求出联通块内每个点到当前根的线性基 一条路径的答案应该在路径出现上第一个成为根的点时统计到 具体来说，就是路径的两端点在同一个solve函数的不同子树内 通过奇怪的时间戳标记可以实现 对于询问，每个结点开个vector暴力遍历即可 由于每个结点最多被dfslog遍，所以复杂度是对的 复杂度瓶颈在dfs求线性基上，时间复杂度

n

l

o

g

2

n

YBTOJ&洛谷P3292：幸运数字（线性基、点分治/倍增）最先出现在Python成神之路。