2月学习目录
1.lxl<基础树上问题>
- 树上差分 （查子树维护单点值） 边差分
-2f(LCA) 点差分-f(LCA)-f(fa[LCA] )- 高效维护子树内点的信息 维护树上颜色种类
- 树链剖分 （重链剖一条路径成logn段序列）将序列搬到树上要注意合并两段序列的端点处
- 常用技巧：离线处理询问（先将树建出来、询问离线）
-
-
换根+询问 通过根节点
rt 和询问节点u 的关系分类讨论习题：
- 洛谷树
- 旅行
- COCI dijovak
2.数学
线性基
-
贪心，从高位到低位
支持
-
- 插入
-
- 查询一个数xor的max
例题： 最大XOR路径
其他操作
1.线性基合并：[幸运数字]()
2.带删除线性基：lvar ref
3.带消元：查询某个数在线性基中的排名 albus
期望：[NOI2012 迷失游乐园]()
容斥：[COCI2006 XOR]()
3.图论
Kruskal重构树
新建节点具有dfn序，可以支持关于"时间"的查询，这里的时间也可以是最小生成树中的权值
两个点之间的所有简单路径上最大边权的最小值 = 最小生成树上两个点之间的简单路径上的最大值 = Kruskal 重构树上两点之间的 LCA 的权值。
虚树
4.根号算法
根号分治