===== 树上莫队 =====
总结时用到的博客:
[[https://blog.csdn.net/qq_39759315/article/details/88553210|https://blog.csdn.net/qq_39759315/article/details/88553210]]
[[https://www.cnblogs.com/RabbitHu/p/MoDuiTutorial.html|https://www.cnblogs.com/RabbitHu/p/MoDuiTutorial.html]]
==== 分块方式 ====
首先需要解决$bzoj1086$王室联邦,此题的解法即为分块的方法
下只简述过程,每块内的节点个数在$[B,3B]$之间,操作方式为维护一个栈,从根节点开始$dfs$,对于某一点$x$:
- 记录栈底的位置$flg$;
- 先访问所有子树,若访问完某棵子树后$top-flg\ge B$,则将$stack[flg+1]$至$stack[top]$中的点分为一块;
- 再将$x$压入栈。
最后栈中剩余的点加入最后一个块中
==== 树上莫队的具体操作 ====
* 带修改问题对时间的排序方式与普通莫队相同
=== 在序列上操作 ===
* 欧拉序
$dfs$遍历序列,当访问到结点$i$时加入序列,回溯至$i$时再将$i$加入序列
* 定义$in[i]$表示在欧拉序$A$中第一次出现的位置,$out[i]$表示$i$第二次的位置
对于路径$x$到$y$上的询问,不妨设$in[x]