rldcot

lxl 上课讲的题，来写个题解。 样例很强，赞美 lxl！青蛙，呱 ????。 \(\text{rldcot} = \text{range lca depth count on tree}\)。/yiw（猜的）。 题目传送门 给出一棵 \(n\) 个点的有根树。定义 \(\text{LCA}(x,y ......

P7880 [Ynoi2006] rldcot 题意 区间虚树数颜色。 题解 十分好的一道题目，绕来绕去又绕回最初的思路了。 首先考虑怎么写出 \(O(nq)\) 的暴力，显然就是扫描树上的每一个点，然后判断有没有点跨子树。 然后考虑到我们求的是虚树颜色数，所以考虑莫队，删除和插入都可以通过找前驱和 ......

我们先不考虑 $dep$ 的问题，先来研究有多少种不同的 $lca(i,j)$。 考虑改询问为贡献，计算一个 $l$ 可以成为哪些 $(i,j)$ 的 lca。这个东西可以写成若干个点对对吧，倘若我们忽略掉一共有 $O(n^2)$ 个点对的事实的话，我们的问题就转化成了有若干个被染成某些颜色的区间， ......