Warning: session_start(): open(/tmp/sess_983bcfa092b1675fb29a317478cd8d42, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
===== 树上莫队 =====
总结时用到的博客:
[[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]