[USACO15DEC]最大流Max Flow

题目描述

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

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

输入格式
The first line of the input contains NN and KK.

The next N-1N−1 lines each contain two integers xx and yy (x \ne yx≠y) describing a pipe

between stalls xx and yy.

The next KK lines each contain two integers ss and tt 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

每次改变树上一个区间的值，很明显的树上差分，我们通过lca来维护既可以了。

可以树链剖分来做，但是效率没树上差分高，而且难写。

树上差分分为 点差分 和 边差分 。

若操作a，b连个点之间加一

点差分：我们每次让a节点加一，b节点加一，lca（a，b）减一，f[lca(a,b)][0]减一。
边差分：我们每次让a节点加一，b节点加一，lca（a，b）减二。

最后统计答案dfs一次即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+10;
int n,k,lg[N],h[N],p[N],f[N][30],res;
int head[N],nex[N<<1],to[N<<1],tot;
inline void add(int a,int b){
	to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
void dfs(int x,int fa){
	h[x]=h[fa]+1;	f[x][0]=fa;
	for(int i=1;(1<<i)<=h[x];i++)	f[x][i]=f[f[x][i-1]][i-1];
	for(int i=head[x];i;i=nex[i]){
		if(to[i]!=fa)	dfs(to[i],x);
	}
}
inline int lca(int x,int y){
	if(h[x]<h[y])	swap(x,y);
	while(h[x]>h[y])	x=f[x][lg[h[x]-h[y]]-1];
	if(x==y)	return x;
	for(int i=lg[h[x]]-1;i>=0;i--)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
void out(int x,int fa){
	for(int i=head[x];i;i=nex[i]){
		if(to[i]==fa)	continue;
		out(to[i],x);
		p[x]+=p[to[i]];
	}
	res=max(p[x],res);
}
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)	lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	for(int i=1;i<n;i++){
		int x,y;	cin>>x>>y;	add(x,y);	add(y,x);
	}
	dfs(1,0);
	while(k--){
		int a,b;	cin>>a>>b;	int c=lca(a,b);
		p[a]++;	p[b]++;	p[c]--;	p[f[c][0]]--;
	}
	out(1,0);
	cout<<res<<endl;
	return 0;
}