[USACO15DEC]最大流Max Flow
更好的阅读体验
[USACO15DEC]最大流Max Flow

题目概括

题目描述

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.

输出格式

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

输入输出样例

输入样例 #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 50,000$

$1 \le K \le 100,000$

解题报告

题意理解

1. 一棵树，根节点为$1$
2. 大量修改操作，但是每次是将两个点之间的路径上的所有点，都增加$1$
3. 一个查询操作，问最后哪一个点上的值最大。

算法解析

首先分析算法，我们发现这道题目还算好，修改操作比较特殊。

因此我们不需要用树链剖分，只需要使用树上差分+最近公共祖先即可。

树上差分，实际上就是子树之间的差分。

或者说，就是一个点上的最后权值，就是统计子树和的过程。

对于本题目而言，我们可以这样进行修改操作。
$$ date[x]++; \\\\ date[y]++; \\\\ date[Lca]– \\\ date[fa[Lca]]– $$
这样我们可以使得，这个修改操作，只会在路径上产生影响，而不会在其他地域产生影响。

其实本题目和之前的Lca算法复习，内容是一模一样的，但是可以作为两个博文，主要是因为，题目不一样。这似乎不太好，但是我们主要是复习每一算法的内容以及模板。

博主最近算法复习，算法难度偏低，内容偏简单，博文偏简略，也是因为$CSP$将至，所以不得已。

毕竟是算法复习，对吧！

代码解析

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+20;
vector<int> g[N];
int fa[N][21],deep[N],date[N],n,k;
void dfs(int x,int s)
{
    deep[x]=deep[s]+1;
    for(int i=0; fa[x][i]; i++)
        fa[x][i+1]=fa[fa[x][i]][i];
    for(int y:g[x])
    {
        if (y==s)
            continue;
        fa[y][0]=x;
        dfs(y,x);
    }
}
inline int Lca(int a,int b)
{
    if (deep[a]<deep[b])
        swap(a,b);
    for(int i=20; i>=0; i--)
        if (deep[fa[a][i]]>=deep[b])
            a=fa[a][i];
    if (a==b)
        return a;
    for(int i=20; i>=0; i--)
        if (fa[a][i]!=fa[b][i])
            a=fa[a][i],b=fa[b][i];
    return fa[a][0];
}
inline void Add(int a,int b)
{
    int lca=Lca(a,b);
    date[a]++;
    date[b]++;
    date[lca]--;
    date[fa[lca][0]]--;
}
inline void Query(int x,int s)
{
    for(int y:g[x])
    {
        if (y==s)
            continue;
        Query(y,x);
        date[x]+=date[y];
    }
}
inline void init()
{
    scanf("%d%d",&n,&k);
    for(int i=1; i<n; i++)
    {
        int s,t;
        scanf("%d%d",&s,&t);
        g[s].push_back(t);
        g[t].push_back(s);
    }
    dfs(1,0);
    while(k--)
    {
        int s,t;
        scanf("%d%d",&s,&t);
        Add(s,t);
    }
    Query(1,0);
    int ans=0;
    for(int i=1; i<=n; i++)
        ans=max(ans,date[i]);
    printf("%d\n",ans);
}
signed main()
{
    init();
    return 0;
}