阅读本文要先有求树上最近公共祖先 LCA 的基础。如果尚未掌握，可以点击链接查看我之前的博客，有详细的图解 LCA 求法：https://blog.csdn.net/h_a_o777oah/article/details/160082173

洛谷题目链接：P3128 [USACO15DEC] Max Flow P - 洛谷

注：设节点 u 到节点 v 的最近公共祖先 LCA 是节点 x ，树上的节点 u 到节点 v 的路径指的一般都是节点 u 到节点 x ，再从节点 x 到节点 v 的这条路径。

在处理树上的一些修改，比如将节点 u 到节点 v 的路径上所有的进行一次修改，如果我们只是一步一步地一个点一个点地慢慢修改，那这个修改速度可就是 O(n) 了。这显得就太慢，这个速度肯定是不满意的。

而在线性数组里，我们处理这种范围的修改利用的就是差分的思想；同理，到树这个数据结构同样可以利用差分的思想，让我们修改的速度来到 O(1) 。

点差分

前缀和与差分是不可分割的关系。在了解树上差分之前，我们还需要了解在树上类似“前缀和”做法。在线性的数组中，前缀和表现为前 n 个元素的和；而在树上则表现为对于节点 u 的前缀和则是他自身的值加上它对应的所有子树的和。其实这更像是对整一棵树做一次后序遍历的求和。如下图所示：

实际上树上做这个前缀和的方法还是很好理解的。而对于差分，我们可以设想一下，如果我们对一棵完全空白的树的某一个节点加上 1 会怎么样？

对于这个树，我们尝试在节点 6 加上 1 。然后再做一次前缀和看看变化如何。

可以发现，由于这个树上前缀和的性质，天然决定了我们只要对原数组作出修改，那进行了树上前缀和之后，从被修改的节点往上一直走的节点直到根节点都会被做出同样的修改！我们只要在差分数组上做出我们需要的修改，那我们最终做一次前缀和就能还原出原数组了。

所以树上的差分数组和一维线性差分的数组都有一个性质就是可以对一个范围进行一个快速的修改。设差分数组为 d ，在一维线性数组我们修改区间 [L,R] 就只需要进行对 d[L] 和 d[R+1] 的修改。这是因为在线性数组里，对每一个点的修改都会影响到后面全部的值。修改 d[L] 的值会对 d[L] 后面的全部原值都造成影响。比如在 d[L] 加 1 ，前缀和得到原数组就能发现 L 后面的所有数值都加了 1 。

而在树上差分数组，我们只要对一个节点进行了修改，它一直往上溯源直到根的节点都会被修改，而我们可以选择一个我们需要的点进行“截断”修改。比如我们需要对节点 8 到节点 2 的路径上节点（即 8,6,2）都加 1 ，我们只需要进行 ++d[8] 和 --d[1] 即可。因为 1 是节点 2 再往上的父节点，超过节点 2 就需要截断不再上传修改了。这和一维差分数组是类似的。

知道了这些，那这个洛谷 p3128 就很简单了，他需要对给出的任意节点 u 到节点 v 的路径上所有点进行统计牛奶量。而且题目给出的 n 个节点且有 n-1 条边，很明显告诉我们这就是一棵树，所以完全可以采用树上差分完成。在树上的路径当然是采用 LCA 来做的，任意两个节点的路径都是其中一个点往上走到它们的 LCA 再向下走到另一个点。所以我们做树上差分，先对节点 u 和 v 进行修改，两个节点都往上传递了修改，在 LCA 处执行截断即可。但是我们仍然要注意一些问题！

比如我们按照上面的树让节点 5 到节点 9 路径上所有点都加 1 观察一下过程。第一步当然是让差分数组 ++d[5] 和 ++d[9] 。如果这样做，以下红色点代表节点 5 影响的范围， 蓝色代表节点 9影响的范围。

可以看到，从它们的 LCA 节点 2 往上的所有节点都受到了两次修改的影响，而我们只需要让 LCA 节点 2 接受一次修改的影响，它往上的父节点都不能受到任何影响。所以我们应该再执行 --d[2] ，先抵消一次 LCA 及以上父节点的一次加 1 影响，执行完如下。

这时它们的 LCA 节点 2 已经满足我们的修改要求了，只进行了一次加 1 修改。而 LCA以上的父节点还没有消除掉影响，所以还要执行一次 --d[1] ，即对 LCA 的 父节点进行一次修改抵消，这样才能最终达成我们的修改要求。

最终如下图，成功对路径上节点 5,2,6,9 全部进行相同的加 1 操作。

所以最终的结果很明显，如果我们想要对任意节点 u 和 v 之间的路径进行每一个点加上一个 val 值，我们只需要对差分数组 d 进行如下四步：

1. d[u]+=val

2. d[v]+=val

3. d[LCA(u,v)]-=val （消除一次影响让对于 LCA 的操作保持为一次）

4. d[LCA(u,v)的父节点]-=val （完全消除对 LCA 之上所有节点的操作影响）

理解了这个，写出以下 P3128 代码也是很简单的了。

#include <bits/stdc++.h>
using namespace std;
vector<int> g[50005];//邻接表存树结构
int n,k;
int f[50005][20];//LCA的用于记录父节点的数组
int d[50005];//LCA节点深度数组
int c[50005];//差分数组，因为我习惯LCA深度数组用d，所以这里随便改用了c
int ans;
void dfslca(int fp,int p,int dep)//LCA初始化用到的DFS
{
    d[p]=dep;
    f[p][0]=fp;
    for(int i=1;i<=18;++i) f[p][i]=f[f[p][i-1]][i-1];
    for(int i:g[p])
    {
        if(i==fp) continue;
        dfslca(p,i,dep+1);
    }
}
int lca(int a,int b)//求LCA的函数
{
    if(a==b) return a;
    if(d[a]<d[b]) swap(a,b);
    for(int i=18;i>=0;--i)
    {
        if(d[f[a][i]]>=d[b]) a=f[a][i];
    }
    if(a==b) return a;
    for(int i=18;i>=0;--i)
    {
        if(f[a][i]!=f[b][i])
        {
            a=f[a][i];
            b=f[b][i];
        }
    }
    return f[a][0];
}
int dfs(int fp,int p)//做前缀和的函数
{
    int sum=c[p];
    for(int i:g[p])
    {
        if(fp==i) continue;
        sum+=dfs(p,i);
    }
    ans=max(ans,sum);//题目要求出流量最大的节点，为方便可以直接边求和边取最大值
    return sum;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<n;++i)
    {
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfslca(0,1,1);
    for(int i=1;i<=k;++i)
    {
        int s,t;
        cin>>s>>t;
        int tlca=lca(s,t);
        //进行四步修改
        ++c[s];
        ++c[t];
        --c[tlca];
        --c[f[tlca][0]];//对LCA的父节点进行修改
    }
    dfs(0,1);//修改完成进行一次前缀和还原
    cout<<ans;
}

边差分

上面这道题目主要是问题是对路径上的节点进行操作，这种叫做点差分；而还有一种情况是与边有关的差分叫边差分。

比如这个题目描述：假设一个物流公司。现有一张由 N 个城市组成的配送网络，结构是一棵树（即 N 个点，N−1 条双向道路）。公司目前有 M 条正在执行的紧急运输任务，每条任务对应树上的一条路径 (,)。需要找出那些 “最繁忙的道路”。所谓最繁忙，是指被 全部 M 条路径共同经过 的道路（即这些路径的交集边）。

这一次就不一样了，我们处理的主体从节点变成了边，所以我们的做法也要相应做出修改了。

对于边我们很难处理，最好当然是把边对应到点上，这样才更好进行操作。所以我们可以定义一条边 (,) ，为父节点，则这条边对应的编号就是节点  。这样的映射也更好让我们后续计算。

我们还是用回上面的树，给对应好的边标上节点的编号。

这个时候就可以沿用一下我们点差分的思想了。我们尝试对节点 5 到节点 8 的上经过的所有的边都加 1 ，表示经过了一次，看看我们该如何计算。

这里我们其实已经把边权对应到点权上了，所以我们也是直接对点进行修改。第一步还是对差分数组 d 进行 ++d[5] 和 ++d[8] 。我们还是用绿色代表 5 ，蓝色代表 8 ，看看这两个修改影响了哪些边。

可以看到，节点 5 和 8 的 LCA 节点 2 这个地方往上的所有点依旧是被操作影响了两次。但是这次我们并不是对点进行操作，我们要修改的主体是边。而 LCA 节点 2 对应的边是更加往上的边，这个边我们根本就不需要修改，我们要修改的边只有编号为 5,6,8 的，所以这里就很简单了，我们之间进行一次 d[LCA(6,8)]-=2 就可以直接截断所有影响，完成修改操作。

所以这一次模拟我们也很容易发现规律了。如果我们像对节点 u 到 v 路径上的所有边权都加上 val ，而且边权都按照我们的定义映射到点权上了，我们只需要对差分数组进行三个操作：

1. d[u]+=val

2. d[v]+=val

3. d[LCA(u,v)]-=2×val （抵消两次修改操作影响）

这么看起来，似乎这个边差分也就更简单了。根据这个我们可以写出以下代码。由于我这个题只是自己瞎编的，只是为了演示边差分，所以代码如果有错误欢迎提出。

#include <bits/stdc++.h>
using namespace std;
vector<int> g[50005];//邻接表存树结构
int n,m;
int f[50005][20];//LCA的用于记录父节点的数组
int d[50005];//LCA节点深度数组
int c[50005];//差分数组，因为我习惯LCA深度数组用d，所以这里随便改用了c
int ans;
void dfslca(int fp,int p,int dep)//LCA初始化用到的DFS
{
    d[p]=dep;
    f[p][0]=fp;
    for(int i=1;i<=18;++i) f[p][i]=f[f[p][i-1]][i-1];
    for(int i:g[p])
    {
        if(i==fp) continue;
        dfslca(p,i,dep+1);
    }
}
int lca(int a,int b)//求LCA的函数
{
    if(a==b) return a;
    if(d[a]<d[b]) swap(a,b);
    for(int i=18;i>=0;--i)
    {
        if(d[f[a][i]]>=d[b]) a=f[a][i];
    }
    if(a==b) return a;
    for(int i=18;i>=0;--i)
    {
        if(f[a][i]!=f[b][i])
        {
            a=f[a][i];
            b=f[b][i];
        }
    }
    return f[a][0];
}
int dfs(int fp,int p)//做前缀和的函数
{
    int sum=c[p];
    for(int i:g[p])
    {
        if(fp==i) continue;
        sum+=dfs(p,i);
    }
    if(p!=1&&sum==m) ++ans;//在这里遍历的时候计数，p!=1排除无意义的根节点
    return sum;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<n;++i)
    {
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfslca(0,1,1);
    for(int i=1;i<=m;++i)
    {
        int s,t;
        cin>>s>>t;
        int tlca=lca(s,t);
        //进行三步修改
        ++c[s];
        ++c[t];
        c[tlca]-=2;
    }
    dfs(0,1);
    cout<<ans;
}