网络分析 参考博客 带权并查集详解

带权并查集（核心）： 1、路压要维护权值（考虑怎么维护） 2、合并时也要维护权值（考虑怎么维护） 3、并查集一般对根节点进行操作

dis与差分： 1、差分是当前元素与前一个元素的差值 ，dis是当前节点与父节点的差值 2、差分做前缀和为原数组 ，dis对祖先做前缀和为原权值

f[x]表示当前x的父亲（未更新）

#include<bits/stdc++.h>
using namespace std;
int const N=1e4+7;
int n,m;
int f[N],w[N],dis[N];  //w表示集合根节点的权值  //dis[i]表示i与父节点（权值）的差值，有点类似差分
int find(int x){
	if(f[x]!=x){
		int fx=f[x];
		f[x]=find(f[x]);
		dis[x]+=dis[fx];   //路压维护权值 //以后难一点的题目，这一步可以画图，举例子，来推出如何维护
	}
	return f[x]; 
}
void merge(int a,int b){
	int fx=find(a),fy=find(b);
	f[fx]=fy;
	dis[fx]=w[fx]-w[fy];   //合并维护权值 //以后难一点的题目，这一步可以画图，举例子，来推出如何维护
}
int main(){
	cin >> n >> m;
	for(int i=1;i<=n;++i) f[i]=i;
	int op,a,b;
	while(m--){
		cin >> op >> a >> b;
		if(op==1){
			if( find(a)!=find(b) ) merge(a,b);
		}
		else w[find(a)]+=b;
	}
	for(int i=1;i<=n;++i){
		cout << w[find(i)]+dis[i] << " ";
	}
	return 0;
}