树上差分

参考资料

• 树上差分 - 前缀和 & 差分 - OI Wiki

例题

P3128 [USACO15DEC] Max Flow P

洛谷 P3128 [USACO15DEC] Max Flow P

Farmer John 在他的谷仓中安装了 $N-1$ 条管道，用于在 $N$ 个牛棚之间运输牛奶（$2 \leq N \leq 50,000$），牛棚方便地编号为 $1 \ldots N$。每条管道连接一对牛棚，所有牛棚通过这些管道相互连接。

FJ 正在 $K$ 对牛棚之间泵送牛奶（$1 \leq K \leq 100,000$）。对于第 $i$ 对牛棚，你被告知两个牛棚 $s_i$ 和 $t_i$，这是牛奶以单位速率泵送的路径的端点。FJ 担心某些牛棚可能会因为过多的牛奶通过它们而不堪重负，因为一个牛棚可能会作为许多泵送路径的中转站。请帮助他确定通过任何一个牛棚的最大牛奶量。如果牛奶沿着从 $s_i$ 到 $t_i$ 的路径泵送，那么它将被计入端点牛棚 $s_i$ 和 $t_i$，以及它们之间路径上的所有牛棚。

参考代码

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

const int N=50005;
vector<int> G[N];
int fa[N],son[N],siz[N],dep[N],top[N];
void dfs1(int u)
{
	siz[u]=1;
	dep[u]=dep[fa[u]]+1;
	for(auto v:G[u])
	{
		if(v==fa[u])continue;
		fa[v]=u;
		dfs1(v);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])son[u]=v;
	}
}
void dfs2(int u,int e)
{
	top[u]=e;
	if(son[u])dfs2(son[u],e);
	for(auto v:G[u])
	{
		if(v==fa[u]||v==son[u])continue;
		dfs2(v,v);
	}
}
int lca(int u,int v)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		u=fa[top[u]];
	}
	return dep[u]<dep[v]?u:v;
}
int a[N],ans=0;
void dfs(int u)
{
	for(auto v:G[u])
	{
		if(v==fa[u])continue;
		dfs(v);
		a[u]+=a[v];
	}
	ans=max(ans,a[u]);
}
int main()
{
	int n,k;
	cin>>n>>k;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs1(1);
	dfs2(1,1);
	while(k--)
	{
		int x,y;
		cin>>x>>y;
		a[fa[lca(x,y)]]--;
		a[lca(x,y)]--;
		a[x]++;
		a[y]++;
	}
	dfs(1);
	cout<<ans<<'\n';
	return 0;
}