随笔：一个有趣的技术

critnos · 2023-08-15 09:13:38 · 算法·理论

昨晚在 u 群看到 EI 的发言，理解了一下感觉很有道理也很有趣，记之。

问题：给定一棵树和一些点对，询问是给一条树边，要你求出任意一对点对满足这个点对在树上形成的路径经过了该树边。树支持 link cut。

考虑这样一个结构：考虑这样一个结构：\forall 2^k\le n 建一棵树，每对关键点 (u,v) 以 \frac 1 {2^k} 的概率选出来，在对应的树的 u\to v 的路径上 xor 上 rd((u,v))（给这条边的编号做一个到 ull 的随机映射）。不过要支持 link cut，所以实际上是给 u,v 两个点 xor 上 rd((u,v))，查询是求断掉一条边之后任意一个子树的 xor 和。如果这条树边对应的 xor 映射到了某个 (u,v) 则查询成功。

那么这个结构会给我们带来怎样的正确率？实际上有一个观察：n 个数，每个数被选择的概率是 \dfrac 1 n，那么恰好选到一个数的概率是 O(1) 的。证明是显然的：\lim_{n\to +\infty}n\times \dfrac 1 n (1-\dfrac 1 n)^{n-1}=\dfrac 1 e。

同理显然有，每个数选择的概率 \dfrac 1 p 满足 n/p 是常数，恰好选到一个数的概率也是 O(1)。

上面的结构是在通过查询的树边的集合 |S| 中尝试恰好选到一个 (u,v)，显然至少存在一棵树满足 \dfrac 1 2<|S|/p<2，即建立 \Theta(\ln n) 个结构就可以有 1-n^{\epsilon} 的正确率。