2020-2021:teams:mian:gary:mos_algorithm_tree
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:mian:gary:mos_algorithm_tree [2020/05/28 22:01] gary |
2020-2021:teams:mian:gary:mos_algorithm_tree [2020/05/28 22:27] (当前版本) gary |
||
|---|---|---|---|
| 行 3: | 行 3: | ||
| 总结时用到的博客： | 总结时用到的博客： | ||
| - | https:%%//%%blog.csdn.net/qq_39759315/article/details/88553210 | + | [[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|https://www.cnblogs.com/RabbitHu/p/MoDuiTutorial.html]] |
| ==== 分块方式 ==== | ==== 分块方式 ==== | ||
| 行 25: | 行 25: | ||
| === 在序列上操作 === | === 在序列上操作 === | ||
| - | <HTML><ul></HTML> | + | * 欧拉序<html><br></html>$dfs$遍历序列，当访问到结点$i$时加入序列，回溯至$i$时再将$i$加入序列 |
| - | <HTML><li></HTML><HTML><p></HTML>欧拉序<HTML></p></HTML> | + | * 定义$in[i]$表示在欧拉序$A$中第一次出现的位置，$out[i]$表示$i$第二次的位置<html><br></html>对于路径$x$到$y$上的询问，不妨设$in[x]<in[y]$ |
| - | <HTML><p></HTML>$dfs$遍历序列，当访问到结点$i$时加入序列，回溯至$i$时再将$i$加入序列<HTML></p></HTML><HTML></li></HTML> | + | * 若$lca(x,y)=x$,统计欧拉序中子序列$A[in[x]],...,A[in[y]]$中的出现过一次的节点的值即可回答询问<html><br></html>可以简单画图证明若是路径上的点当且仅当只其在子序列中只出现一次 |
| - | <HTML><li></HTML><HTML><p></HTML>定义$in[i]$表示在欧拉序$A$中第一次出现的位置，$out[i]$表示$i$第二次的位置<HTML></p></HTML> | + | * 若$lca(x,y)\neq x$,统计欧拉序中子序列$A[out[x]],...,A[in[y]]$中的出现过一次的节点的值以及$lca(x,y)$的值即可回答询问<html><br></html>通过画图会发现$lca(x,y)$并不在序列中，需要额外统计 |
| - | <HTML><p></HTML>对于路径$x$到$y$上的询问，不妨设$in[x]<in[y]$<HTML></p></HTML><HTML></li></HTML> | + | |
| - | <HTML><li></HTML><HTML><p></HTML>若$lca(x,y)=x$,统计欧拉序中子序列$A[in[x]],...,A[in[y]]$中的出现过一次的节点的值即可回答询问<HTML></p></HTML> | + | |
| - | <HTML><p></HTML>可以简单画图证明若是路径上的点当且仅当只其在子序列中只出现一次<HTML></p></HTML><HTML></li></HTML> | + | |
| - | <HTML><li></HTML><HTML><p></HTML>若$lca(x,y)\neq x$,统计欧拉序中子序列$A[out[x]],...,A[in[y]]$中的出现过一次的节点的值以及$lca(x,y)$的值即可回答询问<HTML></p></HTML> | + | |
| - | <HTML><p></HTML>通过画图会发现$lca(x,y)$并不在序列中，需要额外统计<HTML></p></HTML><HTML></li></HTML><HTML></ul></HTML> | + | |
| === 在树上操作 === | === 在树上操作 === | ||
| - | <HTML><ul></HTML> | + | * 直接在树上操作的问题在于并不能类似序列中一样只在左右移动，因而考虑记录一个$vis$数组，表示结点是否在当前处理的路径上，<html><br></html>对于路径$(u_1,v_1)$到$(u_2,v_2)$的转移，只要将路径$(u_1,u_2)$和$(v_1,v_2)$上的点的$vis$值全部取反后在统计答案即可 |
| - | <HTML><li></HTML><HTML><p></HTML>直接在树上操作的问题在于并不能类似序列中一样只在左右移动，因而考虑记录一个$vis$数组，表示结点是否在当前处理的路径上，对于路径$(u_1,v_1)$到$(u_2,v_2)$的转移，只要将路径$(u_1,u_2)$和$(v_1,v_2)$上的点的$vis$值全部取反后在统计答案即可<HTML></p></HTML><HTML></li></HTML> | + | * 需要注意在维护路径上点是并不考虑路径两端点的$lca$，需要将其单独统计,<html><br></html>上述方法的可行性以及不维护$lca$的原因如下(引用VFleaKing的证明) |
| - | <HTML><li></HTML><HTML><p></HTML>需要注意在维护路径上点是并不考虑路径两端点的$lca$，需要将其单独统计，上述方法的可行性以及不维护$lca$的原因如下(引用VFleaKing的证明)<HTML></p></HTML> | + | <HTML><ul></HTML> |
| - | > <HTML><p></HTML>T(v, u) = S(root, v) xor S(root, u)<HTML></p></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><p></HTML>观察将curV移动到targetV前后T(curV, curU)变化：<HTML></p></HTML> | + | |
| - | > <HTML><p></HTML>T(curV, curU) = S(root, curV) xor S(root, curU)<HTML></p></HTML> | + | |
| - | > <HTML><p></HTML>T(targetV, curU) = S(root, targetV) xor S(root, curU) 取对称差：<HTML></p></HTML> | + | |
| - | > <HTML><p></HTML>T(curV, curU) xor T(targetV, curU)= (S(root, curV) xor S(root, curU)) xor (S(root, targetV) xor S(root, curU))<HTML></p></HTML> | + | |
| - | > <HTML><p></HTML>由于对称差的交换律、结合律：<HTML></p></HTML> | + | |
| - | > <HTML><p></HTML>T(curV, curU) xor T(targetV, curU)= S(root, curV) xor S(root, targetV)<HTML></p></HTML> | + | |
| - | > <HTML><p></HTML>两边同时xor T(curV, curU)：<HTML></p></HTML> | + | |
| - | > <HTML><p></HTML>T(targetV, curU)= T(curV, curU) xor S(root, curV) xor S(root, targetV)<HTML></p></HTML> | + | |
| - | > <HTML><p></HTML>发现最后两项很爽……哇哈哈<HTML></p></HTML> | + | |
| - | > <HTML><p></HTML>T(targetV, curU)= T(curV, curU) xor T(curV, targetV)<HTML></p></HTML> | + | |
| <HTML></li></HTML><HTML></ul></HTML> | <HTML></li></HTML><HTML></ul></HTML> | ||
2020-2021/teams/mian/gary/mos_algorithm_tree.1590674465.txt.gz · 最后更改: 2020/05/28 22:01 由 gary
