差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:mian:gary:mos_algorithm_tree [2020/05/15 17:49]
gary 创建
+++ 2020-2021:teams:mian:gary:mos_algorithm_tree [2020/05/28 22:27] (当前版本)
gary
@@ 行 1: / 行 1: @@
-还在总结~
+===== 树上莫队 =====
+总结时用到的博客：
+[[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$压入栈。
+最后栈中剩余的点加入最后一个块中
+==== 树上莫队的具体操作 ====
+  * 带修改问题对时间的排序方式与普通莫队相同
+=== 在序列上操作 ===
+  * 欧拉序<html><br></html>$dfs$遍历序列，当访问到结点$i$时加入序列，回溯至$i$时再将$i$加入序列
+  * 定义$in[i]$表示在欧拉序$A$中第一次出现的位置，$out[i]$表示$i$第二次的位置<html><br></html>对于路径$x$到$y$上的询问，不妨设$in[x]<in[y]$
+  * 若$lca(x,y)=x$,统计欧拉序中子序列$A[in[x]],...,A[in[y]]$中的出现过一次的节点的值即可回答询问<html><br></html>可以简单画图证明若是路径上的点当且仅当只其在子序列中只出现一次
+  * 若$lca(x,y)\neq x$,统计欧拉序中子序列$A[out[x]],...,A[in[y]]$中的出现过一次的节点的值以及$lca(x,y)$的值即可回答询问<html><br></html>通过画图会发现$lca(x,y)$并不在序列中，需要额外统计
+=== 在树上操作 ===
+  * 直接在树上操作的问题在于并不能类似序列中一样只在左右移动，因而考虑记录一个$vis$数组，表示结点是否在当前处理的路径上，<html><br></html>对于路径$(u_1,v_1)$到$(u_2,v_2)$的转移，只要将路径$(u_1,u_2)$和$(v_1,v_2)$上的点的$vis$值全部取反后在统计答案即可
+  * 需要注意在维护路径上点是并不考虑路径两端点的$lca$，需要将其单独统计,<html><br></html>上述方法的可行性以及不维护$lca$的原因如下(引用VFleaKing的证明)
+ <HTML><ul></HTML>
+<HTML><li></HTML> <HTML><p></HTML>T(v, u) = S(root, v) xor S(root, u)<html><br></html>观察将curV移动到targetV前后T(curV, curU)变化： <html><br></html>T(curV, curU) = S(root, curV) xor S(root, curU) <html><br></html>T(targetV, curU) = S(root, targetV) xor S(root, curU) <html><br></html>取对称差： <html><br></html>T(curV, curU) xor T(targetV, curU)= (S(root, curV) xor S(root, curU)) xor (S(root, targetV) xor S(root, curU)) <html><br></html>由于对称差的交换律、结合律： <html><br></html>T(curV, curU) xor T(targetV, curU)= S(root, curV) xor S(root, targetV) <html><br></html>两边同时xor T(curV, curU)： <html><br></html>T(targetV, curU)= T(curV, curU) xor S(root, curV) xor S(root, targetV) <html><br></html>发现最后两项很爽……哇哈哈 <html><br></html>T(targetV, curU)= T(curV, curU) xor T(curV, targetV)<HTML></p></HTML>
+<HTML></li></HTML><HTML></ul></HTML>
+=== 总结 ===
+总结一下树上的操作和序列的不同点
+  - 分块方式不同
+  - 无法直接类比普通莫队序列上的操作，需要通过一些辅助使树上操作变成欧拉序上的操作，或者直接在树上移动，移动是都是通过vis数组判断节点的值是否需要统计(添加或删除)

CVBB ACM Team

用户工具

站点工具

差别

页面工具