Fracture Ray

간선 집합 $F$를 제거했을 때 그래프가 끊어진다는 것은 어떤 공집합이 아닌 컷 $C$가 $F$에 포함된다는 것과 동치이다. $|F|=3$이므로 크기가 $1$, $2$, $3$인 컷만 확인하면 된다.

컷 지문. DFS 스패닝 트리를 하나 잡는다. 각 비트에 대하여 모든 비트가 독립이고 균등한 난수를 사용한다고 생각하자. 트리에 포함되지 않은 각 간선에 독립적인 128비트 값을 주고, 그 값을 두 끝점에 XOR한다. 서브트리 값을 후위 순회로 모으면 각 트리 간선에도 값을 줄 수 있다. 이렇게 얻은 간선의 값을 $h(e)$라고 하자.

모든 컷에 속한 간선들의 $h$를 XOR하면 항상 $0$이다. 컷이 아닌 고정된 간선 집합의 XOR이 우연히 $0$일 확률은 $2^{-128}$ 이하이다. 따라서 세 간선 $e_1,e_2,e_3$을 제거해서 그래프가 끊어지는지는 다음 조건으로 판정할 수 있다.

• 어떤 $h(e_i)$가 $0$이다.
• 서로 같은 두 지문이 있다.
• $h(e_1)\mathbin{\mathrm{xor}}h(e_2)\mathbin{\mathrm{xor}}h(e_3)=0$이다.

세 간선으로 이루어진 연결 단순 그래프의 모양은 별, 길이 $3$인 경로, 삼각형뿐이다.

별. 중심 정점을 $v$라고 하자. $G-v$의 각 연결 요소로 향하는 $v$의 간선들은 하나의 그룹을 이룬다. 별의 세 간선을 제거해서 그래프가 끊어지는 것은 선택한 세 간선이 어떤 그룹 전체를 포함하는 것과 동치이다.

크기가 각각 $1$, $2$, $3$인 그룹 수를 $a,b,c$, $v$의 차수를 $d$라고 하면 답에 더할 별의 수는

$$\binom d3-\binom{d-a}3+b(d-a-2)+c$$

이다. DFS의 low-link 값으로 분리되는 자식 서브트리를 찾을 수 있다. 각 비트리 간선의 조상 끝점에서 다른 끝점으로 내려가는 첫 자식을 이분 상승으로 구하면 모든 그룹 크기도 $O(M\log N)$에 계산할 수 있다.

경로와 삼각형. 간선 $uv$를 가운데 간선으로 고정한다. $u$에 닿은 다른 간선 하나와 $v$에 닿은 다른 간선 하나를 고르면 길이 $3$인 경로는 정확히 한 번, 삼각형은 세 번 센다.

가운데 지문을 $b$, 양쪽 지문을 $x,y$라고 하자. $x$나 $y$가 $0$ 또는 $b$이면 바로 조건을 만족한다. 그렇지 않으면 또는 인 경우만 더하면 된다. 각 정점에서 지문별 등장 횟수를 관리하고, 가운데 간선의 두 끝점 중 차수가 작은 쪽의 간선들만 순회한다. 차수가 큰 정점은 해시 테이블, 작은 정점은 정렬된 배열의 이분 탐색으로 빈도를 구한다. 모든 간선에 대한 작은 쪽 차수의 합은 이다.

삼각형은 차수 순서로 간선을 방향화하여 $O(M\sqrt M)$에 열거한다. 위 컷 조건을 만족하는 삼각형 수를 $Q$라고 하면, 가운데 간선 방식에서 각 삼각형을 세 번 셌으므로 최종 답은

$$(\text{별의 수})+(\text{가운데 간선 방식의 수})-2Q$$

이다.

시간 복잡도는 $O((N+M)\log N+M\sqrt M\log M)$, 공간 복잡도는 이다. 해시 테이블을 사용하는 큰 차수 정점에 대해서는 빈도 질의의 기대 시간 복잡도가 적용된다. 오답 확률은 각 고정된 비컷에 대해 이하이다.

$N$이 작은 경우에는 연결된 세 간선의 모양을 모두 열거하고, 비트리 간선마다 서로 다른 기저 벡터를 주는 정확한 컷 지문으로 확인할 수 있다. 최대 차수가 $\Delta$로 제한되면 별과 가운데 간선의 양쪽 간선을 직접 열거해도 $O(N+M\Delta^2)$에 처리할 수 있다. 나머지 서브태스크에서는 위의 전체 풀이를 사용할 수 있다.

Solution written by GPT6