Skip to main content

树上差分

参考资料​

简介​

树上差分 是差分思想在树结构上的推广，用于高效实现「路径区间加」操作。设差分数组为 DD，对路径 x→yx\to y（设 l=lca⁡(x,y)l=\operatorname{lca}(x,y)，f=fa⁡(l)f=\operatorname{fa}(l)）加 vv：

点差分（将值加到路径上所有节点）：

Dx=Dx+v,Dy=Dy+v,Dl=Dl−v,Df=Df−v.\begin{aligned} D_x & =D_x+v, \\ D_y & =D_y+v, \\ D_l & =D_l-v, \\ D_f & =D_f-v. \end{aligned}

边差分（将值加到路径上所有边，用子节点代表其与父节点之间的边）：

Dx=Dx+v,Dy=Dy+v,Dl=Dl−2v.\begin{aligned} D_x & =D_x+v, \\ D_y & =D_y+v, \\ D_l & =D_l-2v. \end{aligned}

完成所有修改后，做一次 DFS 求子树和，即可得到每个节点/边的累加值。总时间复杂度 O((n+m)log⁡n)O((n+m)\log n)（含倍增 LCA）。

实现​

以下实现点差分，求所有路径经过次数的最大值（P3128 类型）。

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

const int N=50005;
const int LOG=17;
vector<int> G[N];
int fa[N][LOG],dep[N];
int d[N];
void dfs(int u,int f,int depth)
{
	fa[u][0]=f;
	dep[u]=depth;
	for(int i=1;i<LOG;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
	for(auto v:G[u])
	{
		if(v==f)continue;
		dfs(v,u,depth+1);
	}
}
int lca(int u,int v)
{
	if(dep[u]<dep[v])swap(u,v);
	int diff=dep[u]-dep[v];
	for(int i=0;i<LOG;i++)if((diff>>i)&1)u=fa[u][i];
	if(u==v)return u;
	for(int i=LOG-1;i>=0;i--)
	{
		if(fa[u][i]!=fa[v][i])
		{
			u=fa[u][i];v=fa[v][i];
		}
	}
	return fa[u][0];
}
void calc(int u,int f)
{
	for(auto v:G[u])
	{
		if(v==f)continue;
		calc(v,u);
		d[u]+=d[v];
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1,0,0);
	while(m--)
	{
		int s,t;
		cin>>s>>t;
		int l=lca(s,t);
		d[s]++;d[t]++;
		d[l]--;
		if(fa[l][0])d[fa[l][0]]--;
	}
	calc(1,0);
	int ans=0;
	for(int i=1;i<=n;i++)ans=max(ans,d[i]);
	cout<<ans<<'\n';
	return 0;
}

例题​

洛谷 P3128 [USACO15DEC] Max Flow P

给定 NN 个点的树，有 KK 条路径，第 ii 条为 sis_i 到 tit_i。每条路径给沿途（含端点）每个点加 11，求所有点中的最大值。