洛谷 P3128 [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≤N≤50,000), conveniently numbered 1 \ldots N1…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 KK pairs of stalls (1≤K≤100,000). For the iith such pair, you are told two stalls si and ti, 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 si to ti, then it counts as being pumped through the endpoint stalls si and

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

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 N and K.

The next N-1lines each contain two integers x and y (x≠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： 复制

输出样例#1： 复制

没什么好说的了~~树上差分，顺便改了一下我的lca的dfs的写法~整体代码样式自我感觉极度优雅~~QAQ。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
const int DEG = 18;//注意对于不同的题目不同的DEG，~~不过一般都设20就行
int fa[maxn][DEG], sum[maxn], head[maxn], cnt = 0;
int n, m, dep[maxn], ans = 0;
struct *** {
	int ne, v;
}ed[maxn << 1];
void init() {
	cnt = 0; ans = 0;
	memset(head, -1, sizeof head);
	memset(sum, 0, sizeof sum);
}
void add(int u,int v) {
	ed[cnt].v = v; ed[cnt].ne = head[u];
	head[u] = cnt++;
}
void dfs(int u,int f) {
	for (int i = 1; i < DEG; i++)
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for (int i = head[u]; ~i; i = ed[i].ne) {
		int v = ed[i].v;
		if (v == f)continue;
		dep[v] = dep[u] + 1;
		fa[v][0] = u;
		dfs(v, u);
	}
}
int lca(int u, int v) {
	if (dep[u] > dep[v])swap(u, v);
	int hu = dep[u], hv = dep[v];
	int tu = u, tv = v;
	for (int det = hv - hu, i = 0; det; det >>= 1, i++) {
		if (det & 1)
			tv = fa[tv][i];
	}
	if (tu == tv)return tu;
	for (int i = DEG - 1; i >= 0; i--) {
		if (fa[tu][i] == fa[tv][i])continue;
		tu = fa[tu][i];
		tv = fa[tv][i];
	}
	return fa[tu][0];
}
void dfs2(int u,int f) {
	int res = 0;
	for (int i = head[u]; ~i; i = ed[i].ne) {
		int v = ed[i].v;
		if (v == f)continue;
		dfs2(v, u);
		res += sum[v];
	}
	sum[u] += res;
	ans = max(sum[u], ans);
}
int main() {
	while (~scanf("%d%d", &n, &m)) {
		init();
		for (int i = 1; i < n; i++) {
			int a, b;
			scanf("%d%d", &a, &b);
			add(a, b);add(b, a);
		}
		dep[1] = 0; fa[1][0] = 1;dfs(1, 0);
		while (m--) {
			int a, b, c;
			scanf("%d%d", &a, &b);
			c = lca(a, b);
			sum[a]++; sum[b]++; sum[c]--; sum[fa[c][0]]--;
		}
		dfs2(1, 0);
		printf("%d\n", ans);
	}
	return 0;
}