2021年蓝桥杯省赛 E(带权并查集)

题目 题意: 给定n个点，m组操作。输出m次操作后每个点的权值。 操作1: 连接x、y 操作2: 使x及所有与x直接或间接相连的点+y 思路: 带权并查集. 操作2明显是对在一棵树上的所有点进行操作，但是暴力更新肯定寄。 额外开一个数组记录某个点的改变量，操作2只对一棵树的根节点进行操作。最后每个点的权值即 a[find(i)] + d[i]，树根的值 + i到树根的偏移量，偏移量可能是负的。 操作1就正常维护并查集的合并即可。注意新合并的px到父节点py的距离是a[px] - a[py]. 时间复杂度: O(mα(n)) 代码:

#include
using namespace std;
const int N = 1e5+10;
typedef long long ll;
typedef pair PII;
#define fir(i,a,b) for(int i=a;i>n>>m;
	for(int i=1;i>op;
		if(op == 1)
		{
			int x,y; cin>>x>>y;
		    Merge(x,y);
		}
		else
		{
			int x,t; cin>>x>>t;
			int u = find(x);
			a[u] += t;
		}
	}
	for(int i=1;i 1) cout