树上差分

听说这个知识近几年考的挺多,今天来学习一下

简化版:线性序列上的差分

线性序列上的差分就十分常见了,配合前缀和可以支持区间 O(1) 修改,单点 O(n) 查询,配合树状数组可以实现高效的区间查改问题等等

差分上树

  • 树为什么可以差分
    树形结构保证了除根节点外每个节点有且仅有一个父亲节点,并且任意两点之间的路径是唯一的。如果把根节点作为一个端点,叶子节点作为另一个端点,两个端点之间的序列唯一且是一条链,根节点与每个叶子节点之间的路径可以看作是线性序列,而对于单个线性序列可以差分,则对这些线性序列的并也是可以差分的。(当然我们并不会单独用一个数据结构来维护这个序列,利用树形结构的性质以及父子关系就可以维护差分)

  • 树上差分的分类
    树上差分主要分为对于点的差分和对于边的差分

  • 树上差分有哪些经典模型
    给出树上许多路径,要你求出被所有给出路径同时覆盖的边有哪些(树上路径交)
    给出树上许多路径,要你统计每个节点被路径覆盖的次数

  • 把叶子节点看作序列起点还是把根节点看作序列起点
    一般我们把叶子节点看作起点,而把根节点看作终点,这样可以使所有虚拟的差分数组在一处收束,同时这样符合树在进行dfs时回溯顺序

讲解

  • 给出树上许多路径,要你统计每个节点被路径覆盖的次数

因为这道题答案统计只与点权有关,因此是一个典型的的对点差分

洛谷P3128 [USACO15DEC]最大流Max Flow

对于路径 (u,\space v),我们设 lca_{(u,\space v)}uv最近公共祖先,设 dif 为差分数组,我们将 dif_{u}+1,将 dif_{v}+1,将 dif_{lca_{(u,\space v)}}-1,将 dif_{fa_{lca_{(u,\space v)}}}-1
我们在最后统计的时候,把每个点的 ans 初始化为它的 dif ,可以从根节点进行dfs,在回溯的时候把孩子的 ans 加进来(或者从叶子节点开始向根节点进行类似拓扑排序DP的转移),我们保证对于每个节点 i ,有 ans_{i}=dif_{i}+\sum_{j\in son_i}ans_{j},最终每个点的 ans 就是它被覆盖的总次数

  • 给出树上许多路径,要你求出被所有给出路径同时覆盖的边有哪些(树上路径交)

因为这道题答案统计只与边被覆盖次数有关,因此这是一个典型的对边差分

对于路径 (u,\space v),我们设 lca_{(u,\space v)}uv最近公共祖先,设 dif 为差分数组,我们将 dif_{u}+1,将 dif_{v}+1,将 dif_{lca_{(u,\space v)}}-2
我们在最后统计的时侯,把每个点的 ans 的初始值设置为它的 dif 可以从根节点进行dfs,在回溯的时候把孩子的 tot 加进来(或者从叶子节点开始向根节点进行类似拓扑排序DP的转移),我们保证对于每个节点 i ,有 tot_{i}=dif_{i}+\sum_{j\in son_i}tot_{j},每个点的 tot 值就是连接它和它父亲节点的边的被覆盖次数

发表评论

电子邮件地址不会被公开。 必填项已用*标注