04 树上差分：最大流问题

LCA+树上差分 解决最大流问题：Max Flow P

树上差分
树上差分有什么作用？举个例子，如果题目要求对树上的一段路径进行操作，并询问某个点或某条边被经过的次数，树上差分就可以派上用场了。这就是树上差分的基本操作。

树上差分，就是利用差分的性质，对路径上的重要节点进行修改（而不是暴力全改），作为其差分数组的值，最后在求值时，利用dfs 遍历求出差分数组的前缀和，就可以达到降低复杂度的目的。

树上差分时需要求LCA，对点和边的树上差分原理相同，实现略有不同，这里分开来讲。

点差分

设将两点u,v之间路径上的所有点权增加x，o=LCA(u,v),o的父亲节点为p，则操作如下：diff[u]+=x,diff[v]+=x,diff[o]-=x,diff[p]-=x;
怎么样，是不是很简单！原理也很简单，举个例子：

设原树如下，现要将2,3之间路径上的所有点的权值增加3，设原权值均为0。

则操作后有：

这样，只要dfs一遍，遍历时统计以每个节点为根的树的节点的权值和，就是当前节点的最终权值！

边差分

思想一样，讲一下操作。

设将两点u,v之间路径上的所有边权增加x，o=LCA(u,v)，以每条边两端深度较大的节点存储该边的差分数组，则操作如下：

diff[u]+=x,diff[v]+=x,diff[o]-=2*x;

再举个例子，还是上面那个图

则操作后有：

同样地，只要dfs一遍，遍历时统计以每个节点为根的树的节点的权值和，就是当前节点到父亲节点的边的最终权值了！

例题：

[USACO15DEC] Max Flow P

题目描述

Farmer John has installed a new system of $N-1$ pipes to transport milk between the $N$ stalls in his barn ($2 \leq N \leq 50,000$), conveniently numbered $1 \ldots N$. Each pipe connects a pair of stalls, and all stalls are connected to each-other via paths of pipes.

FJ is pumping milk between $K$ pairs of stalls ($1 \leq K \leq 100,000$). For the $i$th such pair, you are told two stalls $s_i$ and $t_i$, endpoints of a path along which milk is being pumped at a unit rate. FJ is concerned that some stalls might end up overwhelmed with all the milk being pumped through them, since a stall can serve as a waypoint along many of the $K$ paths along which milk is being pumped. Please help him determine the maximum amount of milk being pumped through any stall. If milk is being pumped along a path from $s_i$ to $t_i$, then it counts as being pumped through the endpoint stalls $s_i$ and

$t_i$, as well as through every stall along the path between them.

FJ 给他的牛棚的 $N$ 个隔间之间安装了 $N-1$ 根管道，隔间编号从 $1$ 到 $N$。所有隔间都被管道连通了。

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

输入格式

The first line of the input contains $N$ and $K$.

The next $N-1$ lines each contain two integers $x$ and $y$ ($x \ne y$) describing a pipe

between stalls $x$ and $y$.

The next $K$ lines each contain two integers $s$ and $t$ describing the endpoint

stalls of a path through which milk is being pumped.

第一行输入两个整数 $N$ 和 $K$。

接下来 $N-1$ 行每行输入两个整数 $x$ 和 $y$，其中 $x \ne y$。表示一根在牛棚 $x$ 和 $y$ 之间的管道。

接下来 $K$ 行每行两个整数 $s$ 和 $t$，描述一条从 $s$ 到 $t$ 的运输牛奶的路线。

输出格式

An integer specifying the maximum amount of milk pumped through any stall in the barn.

一个整数，表示压力最大的隔间的压力是多少。

样例 #1

样例输入 #1

5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5
3 4

样例输出 #1

9

提示

$2 \le N \le 5 \times 10^4,1 \le K \le 10^5$

以下程序中power为每个点流量大小的差分

对于每一次要求的两个端点，先用LCA算法求出其LCA，再对power的差分数组进行++和–操作，以下内容为主函数的一部分：

    int x,y;
cin>>n>>k;
for(int i=1;i<=n-1;i++)
{
    scanf("%d %d",&x,&y);
    ipoint[x].emplace_back(y);
    ipoint[y].emplace_back(x);
}
for(int i=1;i<=n;i++)
{
    lg2[i]=lg2[i-1]+(1<<lg2[i-1]==i);
}
predfs(1);
while(k--)
{
    scanf("%d %d",&x,&y);
    int lca=LCA(x,y);
    ++power[x];++power[y];
    --power[lca];--power[fa[lca][0]];
}

然后使用深度优先搜索实现对每一个节点的子树的差分数组求和操作，同时在算完每一个点时候，使用ans来统计最大流

在主函数中写：dfs(1);

void dfs(int nowpoint,int father=0)
{
    for(auto ip: ipoint[nowpoint])
    {
        if(ip!=father)
        {
            dfs(ip,nowpoint);
            power[nowpoint]+=power[ip];
        }
    }
    ans=max(ans,power[nowpoint]);
}

最后输出ans即可

完整代码如下：

#include<iostream>
#include<vector>
#define int long long
using namespace std;
const int N=1e5+5;
vector<int> ipoint[N];  
int n,k,depth[N],fa[N][17],lg2[N]={0},power[N]={0},ans=-1e7;
void predfs(int nowpoint,int father=0)
{
    depth[nowpoint]=depth[father]+1;
    fa[nowpoint][0]=father;
    for(int i=1;i<=lg2[depth[nowpoint]];i++)//1
    {
        fa[nowpoint][i]=fa[fa[nowpoint][i-1]][i-1];
    }
    for(auto ip :ipoint[nowpoint] )
    {
        if(ip!=father)
        {
            predfs(ip,nowpoint);
        }
    }
}
int LCA(int x,int y)
{
    if(depth[x]<depth[y])
    {
        swap(x,y);
    }
    while(depth[x]>depth[y])
    {
        x=fa[x][lg2[depth[x]-depth[y]]-1];
    }
    if(x==y)return x;
    else
    {
        for(int i=lg2[depth[x]]-1;i>=0;--i)
        {
            if(fa[x][i]!=fa[y][i])
            {
                x=fa[x][i];
                y=fa[y][i];
            }
        }
    }
    return fa[x][0];
}
void dfs(int nowpoint,int father=0)
{
    for(auto ip: ipoint[nowpoint])
    {
        if(ip!=father)
        {
            dfs(ip,nowpoint);
            power[nowpoint]+=power[ip];
        }
    }
    ans=max(ans,power[nowpoint]);
}
signed main(void)
{

    int x,y;
    cin>>n>>k;
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d %d",&x,&y);
        ipoint[x].emplace_back(y);
        ipoint[y].emplace_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        lg2[i]=lg2[i-1]+(1<<lg2[i-1]==i);
    }
    predfs(1);
    while(k--)
    {
        scanf("%d %d",&x,&y);
        int lca=LCA(x,y);
        ++power[x];++power[y];
        --power[lca];--power[fa[lca][0]];
    }
    dfs(1);
    cout<<ans<<endl;
    return 0;
}