分析考虑并查集。对于\(a_i,b_i,d_i\)，若\(a_i,b_i\)在之前的满足要求的操作中，\(a_i,b_i\)不在同一个集合里，则在之前\(X_{a_i},X_{b_i}\)的相对差值是可以任意改变的。令\(k=X_{a_i}-X_{b_i}\)，则我们需要将\(a_i\)所在集合中所有元素的值增加\(d_i-k\)。然后将\(a_i,b

思路带权并查集模板。如果对于一个三元组\((a,b,c)\)如果它能够添加到\(S\)中一定满足如下条件中的一条：\(X_a,X_b\)满足其中有一个是「不确定」的。在这里\(X_i\)「不确定」指\(X_i\)没有与其它的任意\(X_j\)有关系。\(X_a,X_b\)有间接或直接的关系，但是能计算

原题链接洛谷题面提交记录闲话赛场就做了这道和A，喜提\(625\)大分。带权并查集练手题，有点像银河英雄传说。题目大意存在一个长度为\(N\)的数列\(X\)，给定\(Q\)个三元组\((a_i,b_i,d_i)\)，定义一个好集合为集合\(S\subseteq\{1,2,\dots,Q\}\)，使得所有\(x\inS\)满

blog。提供一个普通并查集+启发式合并做法。考虑直接维护\(X_i\)。对于\(X_u-X_v=w\)，分四种情况。\(X_u,X_v\)都没被维护过。直接钦定\(X_u\getsw,X_v\gets0\)，以后再改。\(X_u\)没被维护过，\(X_v\)被维护过。显然\(X_u\getsX_v+w\)。\(X_v\)没被维护过，\(X_u\)被