最近翻了一下自己的 U 盘, 突然发现有一个树上差分的 ppt, 居然还没有学, 因为以前以为这个很高大尚, 以为很难.......(其实真的不难)
好吧, 入正题
首先得知道差分这个东西吧! 简单差分 http://www.cnblogs.com/cjoierljl/p/8728110.html
在讲树上差分之前, 首先需要知道树的以下两个性质:
(1) 任意两个节点之间有且只有一条路径.
(2) 一个节点只有一个父亲节点 (即只有一条返祖边)
可以发现所有树上两点 a,b 的路径可拆为: a--->LCA(a,b),LCA(a,b)--->b(最好去学一下 LCA 的快速求法 (这个我没写, 随便上网找了一个感觉比较好的: 倍增 LCA 详讲 https://blog.csdn.net/lw277232240/article/details/72870644 ))
首先一个大前提 (一个点的真实权值是一个点子树内所有差分后的权值之和)
自己画一棵树 (不想画图了我), 找两个点 p,q, 如果是要在他们的路径上都加一个 x 的话
你先自己推一下在哪里 ++, 哪里 -- 来维护吧.(注意: 一个点的真实权值是一个点子树内所有差分后的权值之和)
好的,
是在 p,q 上分别 ++, 在 LCA(p,q) 和 fa[LCA(p,q)](LCA(p,q) 的爸爸) 上 --. 自己在去手玩一下吧, 最后统计出来是对的!
这个其实真的不难把!
总结一下:
1. 树上差分主要用于求解一些树上的路径问题
2. 它通过利用树的一些性质, 用一个差分数组来实现对一条路径的操作, 这涉及到路径的 起 终点 与 LCA.
3. 一般情况下: 一个点的真实权值为其所在子树内所有点的差分数组的值的和
4. 树上差分一般不适用于询问和操作嵌套的题目, 这时一般用树链剖分解决
几道题:
1.luoguP3128 [USACO15DEC] 最大流 Max Flow https://www.luogu.org/problemnew/show/P3128 题解 http://www.cnblogs.com/cjoierljl/p/8728040.html 板子题
2.luoguP3258 [JLOI2014] 松鼠的新家 https://www.luogu.org/problemnew/show/P3258 题解 http://www.cnblogs.com/cjoierljl/p/8728194.html 板子题
3.luoguP2680 运输计划 https://www.luogu.org/problemnew/show/P2680 挖个坑
4.luoguP1600 天天爱跑步 https://www.luogu.org/problemnew/show/P1600 挖个坑
来源: http://www.bubuko.com/infodetail-2552097.html