PS 일지 (2024.03.24)

B. 트리와 XOR

내가 트리에 좀 약하다는 걸 알고 있기 때문에 도전해봤다.

문제는 어떤 트리가 주어진다. 각각의 노드 $v_i$에는 정수 $a_i$가 적혀있다.
모든 $a_i$를 같게 만들어야 한다.

이때 한 점에 대해서 연산 $[v_i,c]$를 시행하면 $v_i$를 루트로 하는 서브트리에 대한 모든 정점 $j$에 대해 $a_j$를 $a_j \oplus c$로 변경한다. $\oplus$는 bitwise XOR을 의미한다.

이때의 비용은 $s\cdot c$이다.

$r$번 정점이 트리의 루트일 때 목표를 달성하기 위한 최소 비용을 $m_{r}$이라 할 때, $m_{1}, m_{2}, \ldots, m_{n}$을 구하는 문제이다.

풀이에 앞서

• 정수 $A$와 $B$가 있을 때, $B\oplus c$가 $A$가 되게 하는 $c$는 $A\oplus B$이다.
• $A$와 $B$가 서로 다른 정수라면 $A\oplus c$와 $B\oplus c$또한 서로 다른 정수이다.
• 그리고 그 둘을 bitwise XOR한 값은 동일하다. $(A\oplus c)\oplus(B\oplus c)$는 결합법칙과 교환법칙에 의해 $A\oplus B$이기 때문이다.

풀이 과정

결국 문제가 모든 $a_i$를 같게 만들어야 하므로, 우리는 정점 간에 다음 값을 구해야만 한다.

루트 노드의 번호를 $r$라고 하고, $i$번째 정점의 부모를 $p(i)$라고 할 때 다음과 같다.

어차피 본인보다 상위 정점에서 연산을 해봤자 $(a_i \oplus a_{p(i)})$ 값 자체는 변하지 않기 때문이다.

그럼 이 문제는 결국 $s_i$를 잘 구하면 되는 문제로 변형된다.

일단 루트 노드 $v_r$에서 $m_r$을 구했다고 가정하자.

이때, $v_r$의 자식 중 하나를 $v_s$라고 하면, $m_s$를 구할 때 변하는 건 트리의 크기뿐이다.

$v_s$를 루트노드라고 하면, 원래 $v_s$를 루트로 하는 서브트리의 크기($s_s$)를 변경된 트리에서 $v_r$을 루트로 하는 서브트리의 크기($s_r$)로 바꿔주기만 하면 된다.

그럼 다음 식으로 $m_s$를 구할 수 있다.

$s_r$과 $s_s$는 한 개의 간선으로 나뉘어지는 노드의 개수이다. 따라서, 이는 각 간선마다 미리 구해둘 수 있다. ($O(N)$)