P3128 [USACO15DEC] Max Flow P

#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10;
int n;
int read() {//快读
	char c = getchar(); int x = 0, f = 1;
	for (; c > '9' || c < '0'; c = getchar()) if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
vector<int> g[N];//存图
//树链剖分模板
int dep[N], fa[N], sz[N], son[N];
void dfs1(int u, int father) {
	dep[u] = dep[father] + 1;
	sz[u] = 1; fa[u] = father;
	for (auto v : g[u]) {
		if (v == father) continue;
		dfs1(v, u);
		sz[u] += sz[v];
		if (sz[son[u]] < sz[v]) son[u] = v;
	}
}
int cnt, id[N], top[N];
void dfs2(int u, int t) {
	top[u] = t; id[u] = ++cnt;
	if (!son[u]) return;
	dfs2(son[u], t);
	for (int v : g[u]) {
		if (v == son[u] || v == fa[u]) continue;
		dfs2(v, v);
	}
}
//树状数组模板
int a[N];
void add(int x,int k) {
	for (; x <= n; x += x & -x) {
		a[x] += k;
	}
}
int ask(int x) {
	int ans = 0;
	for (; x; x -= x & -x) {
		ans += a[x];
	}
	return ans;
}
void add_path(int u, int v) {
	while (top[v] != top[u]) {
		if (dep[top[u]] < dep[top[v]]) swap(u, v);//一定要注意是dep[top[u]],一开始写成dep[u]，调试了半天
		add(id[top[u]],1),add(id[u]+1,-1);//利用差分思想
		u = fa[top[u]];
	}
	if (dep[u] < dep[v]) swap(v, u);
	add(id[v],1),add(id[u]+1,-1);
}


int main() {
	int m;
	n=read();m=read();
	for (int i = 1; i < n; i++) {
		int x=read(), y=read();
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs1(1,0);
	dfs2(1, 1);
	while (m--) {
		int u=read(), v=read();
		add_path(u,v);
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		ans = max(ans, ask(i));//寻找最大值
	}
	cout << ans;
	return 0;
}