自动搬运

查看原文

来自洛谷，原作者为

	Yashajin_Ai 夜叉神天衣--Yashajin_Ai

搬运于2025-08-24 22:41:40，当前版本为作者最后更新于2023-02-23 15:10:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

发现一个性质：最多只会合并 $n-1$ 次（类似树只有 $n-1$ 条边）。

于是在合并的时候暴力统计即可。

时间复杂度 $O(n^2+m)$。

建议使用路径压缩和启发式合并。

# include <bits/stdc++.h>
using namespace std;
const int N=10000;
int f[N+10],siz[N+10];
int find(int x){
	if(f[x]==x){
		return x;
	}
	return f[x]=find(f[x]);
}
int val [N + 10], ans [N + 10];
int main () {
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		f[i]=i;
		siz[i]=1;
	}
	while(m--){
		int op,x,y;
		cin>>op>>x>>y;
		switch(op){
			case 1:{
				x=find(x);
				y=find(y);
				if(x!=y){
					for(int i=1;i<=n;++i){
						ans[i]+=val[find(i)];
					}
					for(int i=1;i<=n;++i){
						val[i]=0;
					}
					if(siz[x]>siz[y]) {
						swap(x,y);
					}
					f[x]=y;
					siz[y]+=siz[x];
				}
				break;
			}
			case 2:{
				x=find(x);
				val[x]+=y;
				break;
			}
		}
	}
	for(int i=1;i<=n;++i) {
		cout<<ans[i]+val[find(i)]<<" ";
	}
	return 0;
}