树上差分

本文主要是介绍树上差分，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

[模板题]https://www.luogu.com.cn/problem/P3128

在(u,v)最短路径上每个点加上v,询问最后权值最大的点

const int N = 5e4 + 50,M = 1e5 +50;
int h[N],e[M],ne[M],idx;
void add(int a,int b) {
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int n,m,root;
int dep[N],f[N][31];//i结点的2^j辈祖先
int cf[N];//差分数组,记录结点的子树权值和

void dfs(int u,int fa) {//预处理
	dep[u]=dep[fa]+1;
	for(int i=0; i<30; i++) {  //注意这里不取等号
		f[u][i+1]=f[f[u][i]][i];
	}
	for(int i=h[u]; ~i; i=ne[i]) {
		int j=e[i];
		if(j == fa)continue;
		f[j][0]=u;
		dfs(j,u);
	}
}

int lca(int x,int y) {
	if(dep[x]<dep[y])swap(x,y);
	for(int i=30; i>=0; i--) {   //x,y跳到同一深度
		if(dep[f[x][i]]>=dep[y])x=f[x][i];
		if(x == y)return x;
	}
	for(int i=30; i>=0; i--) {
		if(f[x][i]!=f[y][i]) {
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];//共同的fa
}

int maxn;
void find_ans(int u,int fa) {
	for(int i=h[u]; ~i; i=ne[i]) {
		int j = e[i];
		if(j == fa)continue;
		find_ans(j,u);
		cf[u] += cf[j];   //cf[u]存u结点所有子树的权值和
	}
	maxn = max(maxn,cf[u]);
}

void work() {
	scanf("%d%d",&n,&m);
	memset(h,-1,sizeof(h));
	for(int i=1; i<n; i++) {
		int u,v;scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	dfs(1,0);
	while(m--) {
		int u,v;
		scanf("%d%d",&u,&v);
		int ans = lca(u,v);
		cf[u]++;   //点权差分
		cf[v]++;
		cf[ans]--;
		cf[f[ans][0]]--;
		/*边权差分
		cf[u]+=1;
		cf[v]+=1;
		cf[ans]-=2;
		*/
	}
	maxn = 0;
	find_ans(1,-1);
	printf("%d\n",maxn);
}

这篇关于树上差分的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！