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$가 된다.
수학이 가미된 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$가 된다.
Comments