P3128 [USACO15DEC] Max Flow P（树上差分）

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

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

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

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

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

输出格式

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≤N≤5×104,1≤K≤105

解析：

差分可以便捷的记录一连串的数字相加同一个数。

差分也可以用再树上进行计算路径通过最短点两点个次数。

遍历从1到个个叶子节点的次数。

处理公共祖先和公共祖先的父节点。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e5 + 10,M = 2*N;
int h[N],to[M],ne[M],tot;
int fa[N][22];
int dep[N];
int n,m,ans,power[N];

void add(int a,int b){
	to[++tot] = b,ne[tot] = h[a],h[a] = tot;
}

void dfs(int u,int f){
	dep[u] = dep[f]+1,fa[u][0] = f;
	for(int i = 0;fa[u][i];++i){
		fa[u][i+1] = fa[fa[u][i]][i];
	}
	for(int i  = h[u];i;i = ne[i]){
		if(to[i] != f) dfs(to[i],u);
	}
} 
int lca(int u,int v){ // 最近公共祖先 
	if(dep[u] > dep[v]) swap(u,v); 
	for(int  i = 20;i >=0 ;i--){
		if(dep[u]  <= dep[v]- (1 <<i )){
			v = fa[v][i];
		}
	}
	if(u == v) return u;
	for(int i = 20;i >= 0;i--){
		if(fa[u][i] != fa[v][i]){
			u = fa[u][i],v = fa[v][i];
		}
	}
	return fa[u][0];
}
void dfs2(int u,int f){
	for(int i = h[u];i;i = ne[i]){ //看那个管道压力大 
		int v = to[i];
		if(v == f) continue;
		dfs2(v,u);
		power[u] += power[v];
	}
	ans = max(ans,power[u]);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i = 1,x,y;i < n;i++){
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	dfs(1,0);
	for(int i = 1,x,y;i <= m;i++){
		scanf("%d%d",&x,&y);
		int l = lca(x,y);
		++power[x];++power[y];//这个是遍历到根节点，所以两个++ 
		--power[l];//公共根节点-1  
		--power[fa[l][0]];//父节点再-1    相当于-2因为公共根节点-1了 
	}
	dfs2(1,0);
	printf("%d",ans);
	return 0;
}