树上差分学习笔记

· · 个人记录

前置知识：

1. 差分。

什么是差分？这里就简单来讲解一下，如果有需要可以自行学习（不过来学树上差分的人应该不会连差分都完全不会吧 ）

来看一道例题帮助理解：语文成绩。

题目：

给定 n 个学生的初始成绩。 再给定 q 个形为 l r w 的条件表示下标在 l 到 r 的学生成绩统一增加了 w 。 问最后所以学生中的最低成绩。

解法：

观察到本题只需要区间加减，然后最后查询。 我们维护差分数组：b_i=a_i-a_{i-1}。 每次统一增加时，只要将 b_l+w,b_{r+1}-w 即可。 最后求个前缀和，就是每个人的成绩。

代码：

code

2.LCA

什么是LCA？ LCA 全称“树上最近公共祖先”，即求两个节点在某棵树上深度最大的公共的祖先节点。

模板题：【模板】最近公共祖先（LCA）。

求LCA有多种方法，主要使用的是倍增求 LCA ，树剖求 LCA 以及Tarjan 离线求 LCA 。因为与本文主题距离较远，这里不再赘述其求法，有需要的可以自行学习。

正题：

树上差分，就是把差分应用在了一棵树上。

这里主要分为点差分和边差分。（但是树上差分是一个思想，它总是有很多变形，我们所以主要掌控的是其思想。）

点差分

对于点差分，每次给两点表示将这两点间最短路上的所有点权值 +1，问最后的每个点的权值。

即要求每个点被经过的次数。

我们每次只需要将给出两点的差分值 +1，再将其LCA的差分值 -1，再将LCA的父亲-1。

形象化的，如图：

每个点最后的权值就是以它为根，子树的差分值之和。

[USACO15DEC]Max Flow P

题目：

FJ给他的牛棚的N(2≤N≤50,000)个隔间之间安装了N-1根管道，隔间编号从1到N。所有隔间都被管道连通了。

FJ有K(1≤K≤100,000)条运输牛奶的路线，第i条路线从隔间si运输到隔间ti。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你需要计算压力最大的隔间的压力是多少。

解法：

点差分裸题！对于每个次给出的线路，我们使 c_u+1,c_v+1 ,c_{lca(u,v)}-1,c_{fa_{lca(u,v)}}。

（因为是模板题就在这里放一下代码）


    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        int lca=Lca(x,y);
        c[x]++;c[y]++;
        c[lca]--;c[f[lca][0]]--;
    }

然后我们将每个点所有子树的差分值加起来，就是这个点会被经过的次数。


void dfs2(int x,int fa)
{
    sum[x]=c[x];
    for(int i=head[x];i;i=e[i].nt)
    {
        int to=e[i].to;
        if(to==fa) continue;
        dfs2(to,x);
        sum[x]+=sum[to];
    }
}

因为题目需要你求的是最大的“压力”，所以我们在每个 sum 值中取一个max就可以了。

详细可以看完整代码。

代码：

code

松鼠的新家

题目：

给出一棵树，要求按顺序走完给定的所有点. 每移动一步就要给这次移动经过的点增加1的点权。 求每一个点的最小点权。

解法：

更裸的点差分裸题……于是你把上面的代码复制了一遍，把求 max 的地方去掉，直接输出每个 sum_i。

然后……样例过不去也？！于是我们再仔细思考一下。

要注意的是我们把既作为起点又做为终点的点加了两次，但事实上只会踩到一次，所以最后要把那些点的值减一。

em没明白？看看这张图。

假设我们有两条边，一条沿红色的路径走，一条沿绿色的走，我们想象一下他的走法，从红边走到图中的橙色点，然后在从橙色点出发走绿边。橙色的点事实上只走了一次，但是我们直接把两条边的答案加起来的话，橙色点会被算两次。所以要把这个点的 sum 值 -1 。

Just like this。


    for(int i=2;i<=n;i++)
        sum[a[i]]--;

不同的循环开始的写法这里有所不同（。

代码：

code

边差分

对于边差分，每次给两点表示将这两点间最短路上的所有边的权值 +1，问最后的每个边的权值。（喂这不就是把上面的定义中的点变成边吗？！）

即要求每条边被经过的次数。

维护也和点差分的差不多，不过这里每点表示的是它到它父亲上的边被经过的次数。

我们每次只需要将给出两点的差分值 +1，再将其 LCA 的差分值 -2，即可。

形象化的，如图：

运输计划

题目：

在一颗有边权的树上有m条路径，清零一条边的边权使得m条路径的最大值最小。

解法：

树上边差分裸题（半个）。因为要求最大值最小，这不一看就要加个二分答案吗？！

二分答案，二分什么呢？二分路径的最大长度呀！

具体怎么做呢！？找到一个 mid ，表示我们所有路径长度都必须小于等于这个 mid ，显然当前比我们 mid 长度短的路径一定已经合法，即不用管它们，它们在不用删边的时候就已经满足了条件。

我们需要考虑的肯定是长度大于 mid 的路径。找到被这些路径共同经过的最大的边，如果删去后，这些路径长度都小于 mid，那么这个 mid 就是合法的。

小技巧，我们在删除最大共同边后，可以直接判断原路径中最长的长度是否小于 mid 。因为所有边减去的都是同一条边，所以它们之间的相对长度不会改变，该最长的还是最长。

那么，怎么知道你选择的那条边是被共同经过的呢？每次给给路径上的每个值 +1 ，最后考虑那些边是的值是等于我们选出的路径的总条数！咦？这就到了树上差分的回合啦！

最后，记得每次运行 check 的时候把差分数组初始化！

（听说此题还可以用其他很多方法做，但是这就不在此文的叙述范围了。

代码：

code

写在后面

我们可以发现点差分和边差分唯一的区别是我们让两点 LCA 的差分值再 -1 还是让 LCA 的父亲 -1 。

为什么是这样呢？

因为我们发现从 x 到 y ，我们经过了它们 LCA 的点，但没有经过 LCA 到 LCA 父亲的边。（意会一下）

来点题目

Alyona and a tree

题目：

给你一棵以 1 为根的树，对于每个点 u ，所有在 u 的子树中的点 v ，问距离它的距离不超过 a_v 的节点有多少个？

解法：

发现限制的距离是对于 v 点的，于是我们反向思考，对于每一个点，就考虑它向上能给多少个祖先节点带来收益。

为什么要这样做？我们可以发现因为每一条边的权值均为正数，所以如果点 v 能影响到点 u ，那么它一定可以影响到 v 到 u 路径上点 u 的孩子。相似的，如果点 v 不能影响到 u ，那么它也一定不能影响到 u 的祖先。是的，它有单调性！

那么我们就可以倍增求每个点向上最大能影响到的点。

所以最后怎么统计呢？差分！边差分！

？如果你看了代码问我为什么这题的差分是 ans_u-1,ans_v+1 那么你可以思考一下 u 和 v 的 lca 是什么……显然就是 v ，所以边差分使用的 ans_u+1,ans_v-1,ans_{lca(u,v)}+2 可以转化为上式。

然后就解决了这道题。

代码：

code

Fairy

题目：

给出一张无向图，求删除一条边后此图变成二分图的所有删边种类。

解法：

根据二分图的定义，一个图是二分图当且仅当它没有奇环。

如果一个图中没有奇环，即其本身是一个二分图，那么删除任意一条边都还是二分图。

我们考虑先建一个树出来，然后再考虑不在这个树上的每一条边。

如果现在有一边不在树上，它链接着两点 u 和 v ，我们考虑填上这条边之后会出现奇环还是偶环，那么这个怎么判呢？

我们可以先直接找简单环。

考虑 u 和 v 到数的根节点分别经过了几条边，如果两边都是奇数个或者偶数个，那么我们再添上 u 到 v 的这条边之后一定会出现奇环，反正则是一个偶环。

然后……然后……然后……

我们发现删的边必须是所有奇环经过边，且不能经过一个偶环，因为如果删了这条边，原先的偶环会和奇环连在一起形成大的奇环。

于是必须是被简单奇环经过的，不被简单偶环经过的。

然后就可以用树上差分做了。

代码：

code

——the end——

本文涉及到的题目总览,方便查询练习：

luogu P2367 语文成绩

luogu P3379 【模板】最近公共祖先（LCA）

luogu P3128 [USACO15DEC]Max Flow P

luogu P3258 [JLOI2014]松鼠的新家

luogu P2680 [NOIP2015 提高组] 运输计划

CF739B Alyona and a tree

CF19E Fairy

（感觉我的题目都很简单啊qwq）