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;
}