P7880

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

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