BOJ 28251 - 나도리합

BOJ 28251 - 나도리합

수학이 가미된 DSU문제이다.

어떤 집합 $A,B$ 를 합친다고 하자.

현재 각 집합에서의 정답 값이 $s_A, s_B$ 라고 하고, 내부 원소들의 합을 $c_A, c_B$라 하자.

$A, B$가 합쳐질때는

$c_{A+B}=c_A+c_B$ 가 되고,

$s_{A+B}=s_A+s_B+c_A \cdot c_B$가 된다.