BOJ 32234 - 나무에서 나뭇가지가 다 사라지면?
수능이 두 달도 채 남지 않았지만, PS는 계속됩니다…
| 시간 제한 | 메모리 제한 |
|---|---|
| 1 초 | 1024 MB |
문제
나무에서 나뭇가지가 다 사라지면? 가지런하다
동우와 재우가 $1$번부터 $N$번 정점까지 총 $N$개의 정점으로 이루어진 트리 $T$에서 게임을 한다. 이 트리의 루트는 $1$번 정점이고, $i$번 정점에 $C_i$개의 돌이 있다. 게임은 동우부터 시작해 두 사람이 턴을 번갈아 가며 진행하며, 규칙은 다음과 같다.
현재 A의 턴이라고 가정하자. A는 다음 규칙에 맞는 행동을 한다. 아래의 과정을 한 턴으로 정의한다. 편의상 A가 아닌 다른 사람을 B라 하고, 현재 상태의 포레스트를 $F$라고 하자. 초기에는 포레스트에 $T$ 하나만 있다. 즉, \(F=\{ T \}\)이다.
- A가 현재 상태의 포레스트에 포함된 트리를 하나 고른다. 만약 트리가 남아 있지 않다면 A가 패배한다.
- A가 고른 트리를 $T_0$라 하고, $T_0$의 루트 정점을 $r$이라 하자.
- A가 $T_0$에서 정점 $v$를 하나 골라 $r$과 $v$ 사이의 양 끝점을 포함해 경로 상의 모든 정점을 가져온다. $r=v$인 경우 $r$만 가져온다.
- 이렇게 가져온 정점들에 대하여 B부터 시작해 님 게임을 한다. 즉, 아래와 같이 게임을 한다.
- B부터 시작해 아래 행동을 번갈아한다
- 돌이 $1$개 이상 있는 정점을 하나 골라, 원하는 만큼 돌을 갖고 온다.
- 더 이상 행동하지 못하는 사람이 진다.
- 만약 위와 같이 진행된 님 게임에서 B가 이긴다면, 그 즉시 원래 게임도 B가 이긴다.
- 만약 A가 이겼다면 $T_0$를 다음 규칙에 따라 재배치한다.
- $T_0$에서 $r$과 직접 연결된 정점들에 대하여, 각 정점을 루트로 하는 서브트리를 $F$에 추가한다. 단, $v$를 포함하는 서브트리는 추가하지 않는다.
- $T_0$를 포레스트에서 제거한다.
처음에는 포레스트에 하나의 트리만 존재하지만, 게임을 진행하며 서로 연결되지 않은 여러 개의 트리 집합이 될 수 있다는 점을 유의하자.
자신의 턴에 행동할 수 없는 플레이어가 패배하게 된다. 두 사람이 최적의 방법으로 게임을 진행했을 때, 누가 이기는지 판단해 보자.
입력
첫 번째 줄에 트리의 정점의 개수 $N(1\le N\le 200\, 000)$이 주어진다.
두 번째 줄에 각 정점에 놓여 있는 돌의 개수 $C_1, C_2, \cdots, C_{N}(0\le C_i\le 10^9)$이 공백으로 구분되어 주어진다. 이는 $i$번 정점에 놓여 있는 돌의 개수가 $C_i$개임을 의미한다.
세 번째 줄부터 $N-1$개의 줄에 걸쳐 각 줄마다 트리에서 직접 연결된 두 정점의 번호 $P_i,Q_i(1\le P_i,Q_i\le N$; $P_i\ne Q_i)$가 공백으로 구분되어 주어진다.
주어지는 입력이 트리임이 보장된다.
출력
첫 번째 줄에 동우가 이기면 kidw0124, 재우가 이기면 eoaud0108을 출력한다.
풀게 된 계기
제5회 고려대학교 MatKor Cup: 2024 Summer/Fall 문제들을 모두 풀어보는 중에 만나게 되었습니다.
풀이 과정
이하 내용은 스프라그-그런디 정리와 Small to Large 테크닉에 대한 내용을 설명 없이 사용하고 있습니다.
문제에서 주어진 게임은 스프라그-그런디 정리를 적용할 수 있다는 것을 제일 먼저 생각해볼 수 있습니다. 따라서 각각의 상태(포레스트)에 대응되는 님버(그런디 수)를 찾아 문제에서 주어진 초기 상태의 님버를 구하면 문제를 해결할 수 있습니다.
전체 게임을 생각하기 전에, 비교적 간단한 게임의 4번 과정을 먼저 파악해봅시다. 4번 과정 역시 스프라그-그런디 정리를 이용해 환원하면, ‘루트부터 선택한 정점 사이의 경로상의 모든 정점에 있는 돌의 개수를 xor한 값이 0’인 정점만을 선택할 수 있다는 것을 알 수 있습니다.
이제 어떤 포레스트에 대응되는 님버를 생각해봅시다. 포레스트가 공집합이라면 1번 조건에 따라 대응되는 님버는 자명하게 $*0$입니다. 포레스트에 트리가 여러 개 있다면, 각각의 트리 하나씩을 포함하는 포레스트를 하나의 님 게임으로 생각할 수 있습니다. (편의상 이를 트리에 대응되는 님버라고 하겠습니다.) 결과적으로 전체 포레스트에 대응되는 님버는 각각의 트리에 대응되는 님버를 모두 합(xor)한 값이 된다는 것을 알 수 있습니다.
또한 어떤 트리를 루트의 자식들을 루트로 하는 서브트리들로 쪼개어 생각해 본다면, 서브트리에 대한 님버를 구한 후 그를 통해 전체 트리의 님버를 ‘어떠한 방식’으로 구할 수 있을 것이라고 생각해볼 수 있습니다. 문제에서 트리가 주어지므로 우리가 구해야 할 것은,
- 자식을 가지지 않는 (= 루트로만 구성된) 트리에 대한 님버
- 서브트리의 님버를 통해 전체 트리의 님버를 구하는 ‘어떠한 방식’
이 됩니다.
1. 루트로만 구성된 트리에 대한 님버
이 부분은 비교적 간단합니다. 먼저 루트에 놓여 있는 돌의 개수가 1 이상이라면, 4번 과정에서 어떤 정점도 선택할 수 없습니다. (루트를 선택한다면 B가 승리하게 됩니다.) 따라서 대응되는 님버는 \(*0\)입니다. 반대로, 루트에 놓여 있는 돌의 개수가 0이라면 루트를 선택한 후, 트리를 포레스트에서 제거하여 포레스트를 공집합으로 만들 수 있습니다. 따라서 행동 집합은 \(\{*0\}\), 즉 대응되는 님버가 \(*1\)입니다.
2. 서브트리의 님버를 통해 전체 트리의 님버 구하기
이번에도 역시 루트에 놓인 돌이 1 이상인 경우와 0인 경우를 따로 생각해봅시다.
먼저 1 이상인 경우입니다. 여기서 해당 서브트리를 선택할 수 있는 경우와 아닌 경우, 둘로 나누어 생각해볼 수 있습니다. 선택할 수 있는 서브트리는 4번 과정을 만족하는 정점이 해당 서브트리 안에 존재하는 경우이고, 선택할 수 없는 서브트리는 아닌 것입니다. 다만 이에 대해 생각하려면 복잡하기 때문에, 일단 이것을 빠르게 파악할 수 있다고 가정하고 사고를 전개해봅시다.
여기부터는 예시를 통해 생각하는 것이 수월하기에, 전체 트리 $T$와 그 서브트리 $C_1, C_2, C_3$을 생각해 보겠습니다. 이때 각 서브트리에 대응되는 님버를 임의로, $*1, *2, *3$이라고 하겠습니다. 또한 모든 서브트리를 선택할 수 있다고 가정하겠습니다.
여기서 어떤 서브트리를 선택했을 때 상태가 어떻게 변하는지 생각해 보겠습니다. $C_1$을 선택한다면 6번 규칙에 따라, $C_1$을 제외한 $C_2$와 $C_3$이 포레스트에 추가되고 원래의 $T$는 삭제됩니다. 이때 $C_2$와 $C_3$의 님버가 각각 \(*2, *3\)이라고 했으므로, 해당 상태의 님버는 \(*2 + *3 = *1\)이 됩니다. $C_2$와 $C_3$을 선택하는 경우도 마찬가지로 생각할 수 있습니다. 따라서, $T$의 행동 집합은 \(\{*2+*3, *1+*3, *1+*2\} = \{*1, *2, *3\} = *0\)이 됩니다.
이와 같이, 어떤 트리에 대응되는 행동 집합의 원소는 각각의 선택할 수 있는 서브트리에 대해 그 서브트리를 제외한 다른 서브트리들의 님버의 합이 됩니다. 그리고 행동 집합에 속하지 않는 최소의 음이 아닌 정수(MEX)를 구하면, 전체 트리에 대응되는 님버를 구할 수 있습니다.
루트에 놓인 돌이 0이라도 위의 과정은 동일하게 진행할 수 있습니다. 다만, 이 때는 루트 그 자체를 선택하는 경우까지 고려하여 행동 집합에 모든 서브트리의 님버들의 합도 포함해야 합니다.
그리고 남은 것은 앞에서 건너뛴 ‘어떤 서브트리를 선택할 수 있는지’에 대한 여부입니다. 이를 위해서 트리에 있는 모든 정점에 대해 ‘1번 정점으로부터 해당 정점까지 오는 경로상의 모든 정점에 놓인 돌들의 개수를 xor한 값’을 생각해볼 수 있습니다. 이를 $S_i$라고 하겠습니다. (처음에는 모든 정점이 하나의 트리에 속해있기에 이 값은 항상 정의할 수 있습니다.)
이제 $p$를 루트로 하는 트리와 그 자식 노드 $q$를 루트로 하는 서브트리를 생각해 보겠습니다. $q$에 포함된 모든 정점에 대한 $S_i$ 값을 원소로 하는 집합 $T_q$를 생각해 보겠습니다. $q$ 아래에, $p$에서 $r$까지의 경로상의 모든 돌의 개수를 xor한 값이 0이 되는 정점 $r$이 존재한다고 가정해 보겠습니다. 그렇다면 $S_p \oplus S_r$를 일종의 누적합들의 차로 생각하여, $S_p \oplus S_r = C_p$ ($C_p$는 해당 정점에 놓인 돌의 개수)가 되는 것을 알 수 있습니다. 식을 변형해주면 $S_r = S_p \oplus C_p$가 되고, $S_p \oplus C_p \in T_q$인지 확인해 주면 해당 서브트리를 선택할 수 있는지 여부를 알 수 있습니다. 또한 $T_p$를 구하기 위해 $p$ 아래의 서브트리들의 $T_i$들을 Small to Large 테크닉을 사용하여 합집합할 수 있습니다. 이렇게 구한 $T_p$의 값은 $p$를 포함하는 다른 트리의 님버를 구할 때 활용할 수 있습니다.
마지막으로 위의 내용을 종합하여 값을 구해야 합니다. 각각의 정점에서 구해야 할 것은 ‘해당 정점을 루트로 하는 트리의 님버’와, ‘해당 정점을 루트로 하는 트리 아래의 $S_i$ 값들의 집합’이 됩니다. 각 정점에 대한 $S_i$는 DFS 등을 통해 $O(n)$에 구할 수 있고, DFS를 통해 정점들의 깊이를 파악한 후 깊이가 깊은 정점부터 순회하며 님버와 $T_i$를 $O(n)$과 $O(n \log n)$에 구해줄 수 있습니다. 그 결과 구할 수 있는 1번 정점의 님버가 이 문제의 해답이 됩니다.
마치며
태그에 머지 소트 트리, 세그먼트 트리 등이 달려있어서 조금 겁을 먹었지만 Small to Large 트릭과 스프라그-그런디 정리만 알면 아주 어렵지는 않은 문제였던 것 같습니다. 시간에 쫓겨 뒷부분 설명이 퀄리티가 좋지 못한 점에 대해서는 사과드립니다. 시간이 날 때 조금 수정해 보도록 하겠습니다.