BOJ 23091 Calculate! 3

정점 $X$와 정점 $Y$를 잇는 경로 상의 가중치들의 XOR은 루트에서 정점 $X$까지의 경로의 XOR과 루트에서 $Y$까지의 경로의 XOR을 XOR한 것과 같습니다.

따라서, 다음과 같은 방법으로 쿼리를 처리할 수 있습니다.

• 각 정점의 가중치를 루트에서 그 정점으로의 경로의 XOR로 둡니다.
• Euler tour segment tree를 만들고, 세그 노드에는 구간 내에서 가중치가 0~31인 정점의 개수를 저장합니다.
• 간선의 가중치가 바뀌면 서브트리 내의 모든 점의 가중치가 (기존 가중치 XOR 새로운 가중치)를 XOR한 것으로 바뀝니다. 이는 구간에 XOR할 값을 저장하는 레이지로 관리할 수 있습니다.
• XOR이 $c$인 경로의 개수는 전체 트리에서 가중치가 0~31인 정점의 개수를 쿼리한 다음, $i$의 개수와 $i \operatorname{xor} c$의 개수의 곱의 합을 이용하여 구할 수 있습니다.