推导部分和(蓝桥杯)

我要是早点复习一下带权并查集 当时这个题就能A掉了 啊啊啊啊啊啊心态爆炸

这就是一个带权并查集的模板题啊

给出[l,r]的区间和，相当于s[r]-s[l]

一旦已经知道了 s[a]-s[b],s[b]-s[c]，显然再给出一条[a,c]就可以判断"真假"了

将每条这样的信息(l,r,w)，l,r放入一个集合中，

用并查集来维护，并维护cha[l]=s[root]-s[l],cha[r]=s[root]-s[r]

若 l,r已经在同一个集合中，就直接查询cha[l]-cha[r]，判读与w是否相等

合并操作是灵魂

#include
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=1e5+5;
ll val[maxn];
int fa[maxn];
int n,m,Q;
int find(int x){
	if(x==fa[x])return x;
	int oldfa=fa[x];
	fa[x]=find(fa[x]);
	val[x]+=val[oldfa];
	return fa[x];
}
int main(){
	cin>>n>>m>>Q;
	for(int i=0;i<=n;i++)fa[i]=i; 
    for(int i=1;i<=m;i++){
    	ll L,R,S;
    	cin>>L>>R>>S;
    	L--;
    	int fx=find(L),fy=find(R);
    		fa[fy]=fx;
    		val[fy]=val[L]-val[R]-S;
	}
	while(Q--){
		int L,R;
		cin>>L>>R;
		L--;
		int fx=find(L),fy=find(R);
		if(fx!=fy)
		cout<<"UNKNOWN"<