All Falls Down

각 정점 $v$에 정수 $r(v)$를 다음과 같이 정의한다.

• $v$가 잎이면 $r(v)=0$이다.
• $r(c)$가 짝수인 자식 $c$가 있다면, 그 값의 최솟값에 $1$을 더한다.
• 그렇지 않다면, 모든 자식의 $r(c)$ 중 최댓값에 $1$을 더한다.

이 값은 자식의 값을 모두 구한 뒤 아래에서 위로 계산할 수 있다. $r(v)$가 양의 짝수이면 모든 자식의 값은 홀수이며 그 최댓값은 $r(v)-1$이다. $r(v)$가 홀수이면 값이 $r(v)-1$인 짝수 자식이 존재하고, 모든 짝수 자식의 값은 $r(v)-1$ 이상이다.

현재 말이 $u,v$에 있고 턴을 진행할 사람이 패배하는 조건은 $\min(r(u),r(v))$가 짝수인 것이다. 말이 자식으로 내려갈 때마다 이 명제를 귀납적으로 증명할 수 있다.

$\min(r(u),r(v))=k$가 짝수라고 하자. $k=0$이면 이동할 수 없는 말이 있다. $k>0$이면 값이 $k$인 말의 모든 자식은 값이 $k$보다 작은 홀수이다. 다른 말의 자식 값이 짝수라면 그 값은 $k$ 이상이고, 홀수라면 두 자식 값의 최솟값은 여전히 홀수이다. 따라서 모든 이동은 상대가 이기는 상태로 간다.

반대로 $k$가 홀수라면, 값이 $k$인 말은 값이 $k-1$인 짝수 자식으로 이동할 수 있다. 다른 말의 값이 홀수라면 값이 $k-1$ 이상인 짝수 자식을 고를 수 있다. 다른 말의 값이 짝수라면 값이 $k$ 이상인 홀수 자식을 고를 수 있다. 따라서 두 자식 값의 최솟값이 짝수인 상태로 이동할 수 있다.

Alice가 쌍을 고른 직후 Bob이 먼저 이동하므로, 구하는 쌍은 $\min(r(u),r(v))$가 짝수인 쌍이다. 각 $r$값의 빈도를 세고 큰 값부터 내려오며, 현재 값이 짝수일 때 같은 값을 가진 정점 쌍과 더 큰 값을 가진 정점과의 쌍을 더한다. 답은 $64$비트 정수에 저장한다.

한 케이스의 시간 복잡도와 공간 복잡도는 모두 $O(N)$이다.

Solution written by GPT6