editorial

---

D

summary:

모든 노드에 대해, 그 노드를 루트로 가지는 트리에 다음 연산을 여러번 수행해서 트리의 모든 노드의 a값을 동일하게 만들 수 있는 최소 비용을 구하는 문제이다.

노드 r와 숫자 c를 하나 선택해서 그 r을 root로 하는 subtree의 모든 노드의 값들과 c를 xor시킨다. 그 비용은 subtree의 노드 개수$ \cdot c$이다.

solution:

r을 루트로 하는 subtree의 노드 개수를 $s_r$이라고 하자.

한 트리 T의 a값을 모두 동일하게 만드는 비용은 $\sum_{i \in T, i!=r} \{s_i\cdot(a_i \oplus parent(a_i)) \}$이다.

만약 p와 q가 인접한 노드이고 p가 q의 부모일 때, p에 대해 계산이 완료되었다면 q를 루트로 하는 서브트리에 대한 비용도 구할 수 있다. $O(n)$

p를 루트로 하는 서브트리에서 q를 루트로 바꾸게 되면 p는 q의 자식이 된다. 따라서 $s_r$개의 노드에 대해 p의 자식이 아닌 노드에 대한 비용($s_q \cdot (a_p \oplus a_q) )$을 빼 주어야 하고, q는 이제 자식 노드가 된 q를 제외하고 p를 부모로 가졌던 형제 노드들에 대한 값($(n-s_q) \cdot (a_p \oplus a_q)$)을 더해 줘야 한다. $O(1)$

이 과정을 노드 1에 대해 $O(n)$의 시간 복잡도로 첫 비용을 구하고, 트리를 dfs($O(n)$)하면서 이전 노드에서 구한 최소 비용을 바탕으로 다음 노드를 루트로 가지는 트리의 비용을 계산 ($O(1)$)하면 된다.