Rainbow Spanning Tree

색 집합 $S\subseteq\{1,2,\dots,7\}$에 대하여, $S$에 속한 색 중 적어도 하나로 칠할 수 있는 간선들의 집합을 $E(S)$라 하자. 즉 $E(S)=\{\,e : A_e\cap S\neq\emptyset\,\}$이다. 또한 $r(S)$를 $E(S)$의 간선만 사용하여 만들 수 있는 forest의 최대 간선 수, 즉 $E(S)$ 안에서 사이클 없이 택할 수 있는 간선 수의 최댓값이라 하자.

$r(S)$는 DSU로 계산할 수 있다. 처음에는 모든 정점을 서로 다른 component에 둔다. 간선을 하나씩 보면서, 그 간선이 $S$에 속한 색 중 하나라도로 칠할 수 있으면(즉 $A_e\cap S\neq\emptyset$이면) 양 끝점을 합친다. 이때 실제로 서로 다른 두 component가 합쳐진 횟수가 $r(S)$이다. 색이 7개뿐이므로 비어 있지 않은 색 집합은 $2^7-1=127$개이며, 따라서 모든 $S$에 대하여 $r(S)$를 미리 계산해 둘 수 있다.

판정 조건

spanning tree는 항상 정확히 $N-1$개의 간선을 가지므로, 먼저 $a_1+a_2+\cdots+a_7=N-1$이어야 한다. 이 조건이 성립하지 않으면 답은 No이다. 이 조건이 성립한다고 할 때, 답이 Yes이기 위한 필요충분조건은 모든 색 집합 $S\subseteq\{1,2,\dots,7\}$에 대하여

$$\sum_{j\in S}a_j \le r(S)$$

가 성립하는 것이다.

이 조건의 필요성은 다음과 같이 확인된다. 색 집합 $S$에 속한 색으로 칠해야 하는 간선은 총 $\sum_{j\in S}a_j$개이다. 그런데 색이 $S$에 속하도록 칠해진 간선은 모두 $E(S)$에 속해야 하고, spanning tree의 부분집합이므로 그들끼리도 사이클을 이룰 수 없다. 따라서 그 개수는 $E(S)$ 안의 forest 최대 크기인 $r(S)$를 넘을 수 없다. 즉 $\sum_{j\in S}a_j>r(S)$를 만족하는 색 집합 $S$가 존재하면 답은 No이다.

이제 이 조건이 충분함을 보인다.

증명

간선 집합 위의 독립성을 "사이클을 이루지 않음"으로 정의하면, 독립 집합은 forest이며 그 rank는 해당 간선 집합 내 forest의 최대 크기이다. 이는 곧 graph matroid이다.

Theorem 2.1. Rado's Theorem

matroid $M$의 ground set을 $E$, rank 함수를 $\rho$라 하고, 집합 $A_1,\dots,A_m\subseteq E$가 주어졌다고 하자. 각 $i$마다 $x_i\in A_i$를 택하여 $x_1,\dots,x_m$이 모두 서로 다르고 $\{x_1,\dots,x_m\}$이 $M$에서 독립이 되도록 할 수 있을 필요충분조건은 모든 $I\subseteq\{1,\dots,m\}$에 대하여

$$\rho\Bigl(\bigcup_{i\in I}A_i\Bigr)\ge |I|$$

가 성립하는 것이다.

색 $j$로 칠할 수 있는 간선들의 집합을 $E_j$라 하자(즉 $E_j=E(\{j\})$). 각 색 $j$마다 정확히 $a_j$개의 간선을 선택하되, 선택된 간선들은 전체적으로 서로 다르고 사이클을 이루지 않아야 한다.

각 색 $j$에 대하여 "$E_j$에서 간선 하나를 선택한다"는 요구사항을 $a_j$개 생성한다. Theorem 2.1을 적용하면, 모든 요구사항을 서로 다른 간선으로 만족하면서 전체가 독립(forest)이 되도록 할 수 있을 필요충분조건은, 요구사항들의 임의의 부분집합에 대하여 해당 요구사항들이 선택할 수 있는 간선들의 합집합의 rank가 요구사항의 개수 이상인 것이다.

요구사항들의 부분집합 하나를 택하고, 거기에 등장하는 색들의 집합을 $S$라 하자. 해당 요구사항들이 선택할 수 있는 간선들의 합집합은 $\displaystyle\bigcup_{j\in S}E_j=E(S)$이고 그 rank는 $r(S)$이다. 주어진 색 집합 $S$에 대하여 가장 강한 제약은 $S$에 속한 색의 요구사항을 모두 포함하는 경우에 발생하며, 이때 요구사항의 개수는 $\sum_{j\in S}a_j$이다. 따라서 Theorem 2.1의 조건은 정확히 "모든 $S$에 대하여 $\sum_{j\in S}a_j\le r(S)$"와 동치이다.

이 조건이 성립하면 각 색 $j$에서 정확히 $a_j$개의 간선을 선택하여 전체가 forest가 되도록 할 수 있다. $a_1+\cdots+a_7=N-1$이므로 선택된 간선은 총 $N-1$개이고, 정점이 $N$개인 그래프에서 $N-1$개의 간선을 갖는 forest는 연결되어 있어야 하므로 spanning tree이다. 따라서 조건을 만족하는 spanning tree와 색 배정이 존재한다.

구현과 시간복잡도

정리하면, 한 질의의 답이 Yes이기 위한 필요충분조건은 두 가지이다. 첫째, $a_1+a_2+\cdots+a_7=N-1$이어야 한다. 둘째, 모든 색 집합 $S\subseteq\{1,2,\dots,7\}$에 대하여 $\sum_{j\in S}a_j\le r(S)$이어야 한다.

따라서 각 질의마다 먼저 합이 $N-1$인지 확인하고, 그렇지 않으면 No를 출력한다. 이후 $127$개의 색 집합을 모두 검사하여, 하나라도 위배되면 No를, 모두 만족하면 Yes를 출력한다.

$\sum_{j\in S}a_j$는 bitmask DP로 한 번에 구할 수 있다. 색 $j$를 비트 $j$에 대응시키고, $S$에서 임의의 색 $x$ 하나를 제거하면 $\text{need}[S]=\text{need}[S\setminus\{x\}]+a_x$이므로, 질의 하나당 $O(2^7)$에 모든 $S$에 대한 $\text{need}[S]$를 구할 수 있다.

전체 시간복잡도는 $O(2^7M\,\alpha(N)+2^7Q)$이다. 첫 번째 항은 $127$개의 색 집합 각각에 대하여 DSU로 $r(S)$를 전처리하는 비용이며, 두 번째 항은 각 질의에서 모든 색 집합을 검사하는 비용이다.

Solution by Claude Opus 4.8