P3128 [USACO15DEC] 最大流

Description

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

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

Input

The first line of the input contains N and K.
The next N-1 lines each contain two integers x and y (\(x \neq 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.

Output

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

Sample Input

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

Sample Output

9

思路：
  N个节点构成了一棵树，然后在树上的边有流量，给定一条路线，其所经过的边流量都+1.
  典型的含边权的树上差分。根据树上差分思想，把边的流量保存在儿子节点上，当从u到v有一条路线时，只跟u到v上所有的边有关系，而跟lca(u,v)到根的边全都无关。因而flow[u]++,flow[v]++,flow[lca(u,v)]-=2.
  全部加完后，用一次DFS即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e4+20;
int n,k;
int bei[22],f[maxn],high,tot[maxn];//flow
int d[maxn],fir[maxn],nex[2*maxn],to[2*maxn];
int fa[maxn][22];

inline ll read(){
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x;
}

inline void dfs1(int now,int pre,int depth)//init for lca
{
    d[now]=depth;
    fa[now][0]=pre;
    for(int i=1;i<=20;++i)
        fa[now][i]=fa[fa[now][i-1]][i-1];
    for(int i=fir[now];i;i=nex[i])
    {
        if(to[i]==pre) continue;
        dfs1(to[i],now,depth+1);
    }
}

inline int lca(int x,int y)
{
    if(d[x]<d[y]) swap(x,y);
    for(int i=20;i>=0;--i) if(d[x]-bei[i]>=d[y])
        x=fa[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;--i) if(fa[x][i]!=fa[y][i])
    x=fa[x][i],y=fa[y][i];
    return fa[x][0]; 
}

inline void dfs2(int x,int y)//add values
{
    int l=lca(x,y);
    ++f[x],++f[y],--f[l],--f[fa[l][0]]; 
}

inline void dfs3(int now,int pre)//find the point with highest value
{
    for(int p=fir[now];p;p=nex[p])
    {
        if(to[p]==pre) continue;
        dfs3(to[p],now);
        tot[now]+=tot[to[p]];
    }
    tot[now]+=f[now];
    if(tot[now]>high) high=tot[now];
}

int main()
{
    n=read(),k=read();
    bei[0]=1;
    for(int i=1;i<=20;++i) bei[i]=bei[i-1]*2;
    for(int i=1;i<n;++i)
    {
        int p=read(),q=read();
        nex[i]=fir[p],fir[p]=i,to[i]=q;
        nex[n+i]=fir[q],fir[q]=n+i,to[n+i]=p;
    }
    dfs1(1,0,1);
    while(k--) 
        dfs2(read(),read());
    dfs3(1,0);
    printf("%d\n",high);
    return 0;
}