Luogu3128 [USACO15DEC]Max Flow P

tony102

2021 年 01 月 26 日

1690 次浏览

暂无评论

469字数

题解

[Link](https://www.luogu.com.cn/problem/P3128)

## Sol

karls图论题单里的绿题决定来水一水

我觉得完全可以树剖水过去。但是塔门说，让我讲讲树上差分。我说，“这不是一句话了事的事嘛。”所以我写了树上差分。

这个题是点差分，你就是在$w[u] + 1, w[v]+1,w[lca]-1,w[fa[lca]]-1$就可以了

如果是边查分，$w[u]+1,w[v]+1,w[lca]-2$

会了没有，回答的时候遍历一下记一下最大值了事。

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

const int SIZE = 5e4 + 5;

int n, k, num, ind, ans;
int head[SIZE], w[SIZE], dfn[SIZE], f[SIZE][21];

struct node {
	int to, nxt; 
} edge[SIZE << 1];

namespace ae86 {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (!isdigit(c))b ^= c == '-', c = fetch();
		while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
		return b ? a : -a;
	}
}
using ae86::read;

void addEdge(int u, int v) {
	edge[++ num].to = v, edge[num].nxt = head[u];
	head[u] = num;
}

void dfs(int u, int fa) {
	dfn[u] = ++ ind;
	for (int i = head[u], v; i; i = edge[i].nxt) {
		v = edge[i].to;
		if (v == fa) continue;
		f[v][0] = u;
		for (int j = 1; j <= 20; ++ j) f[v][j] = f[f[v][j - 1]][j - 1];
		dfs(v, u);
	}
}

int lca(int u, int v) {
	if (dfn[u] > dfn[v]) std::swap(u, v);
	if (u == v) return u;
	for (int i = 20; ~i; -- i) {
		if (dfn[f[v][i]] > dfn[u]) v = f[v][i];
	}
	return f[v][0];
}

void modify(int u, int v) {
	int fa = lca(u, v);
	++ w[u], ++ w[v], -- w[fa], -- w[f[fa][0]];
}

int query(int u, int fa) {
	for (int i = head[u], v; i; i = edge[i].nxt) {
		v = edge[i].to;
		if (v == fa) continue;
		query(v, u);
		w[u] += w[v];
	}
	ans = std::max(w[u], ans);
}

int main() {
	// freopen("code.in", "r", stdin);
	n = read(), k = read();
	for (int i = 1, u, v; i < n; ++ i) {
		u = read(), v = read();
		addEdge(u, v); addEdge(v, u);
	}
	dfs(1, 0);
	int u, v;
	while (k --) {
		u = read(), v = read();
		modify(u, v);
	}
	query(1, 0);
	printf("%d\n", ans);
	return 0;
}
```

最后修改：2021 年 09 月 04 日