✧ ✦ 시 험 운 의 불 씨 ✦ ✧

구간 $[L,R]$ 안의 정점과 그 사이의 모든 간선으로 이루어진 유도 부분 그래프를 생각하자.

모든 학생에게 불씨가 도달하려면 이 그래프가 연결되어 있어야 한다. 연결된 그래프에 사이클이 있으면, 시작점에서 사이클에 도달한 불씨가 사이클을 계속 돌 수 있으므로 전달이 끝나지 않는다. 반대로 트리에서는 각 정점까지의 유일한 경로를 따라 불씨가 전달된다. 이때 마지막 전달 시각은 최대 $R-L \le N-1$이므로 시간 조건도 만족한다. 따라서 유도 부분 그래프가 트리인 구간의 수를 세면 된다.

작은 입력에서는 모든 구간을 직접 확인할 수 있다. 각 구간에서 BFS를 실행하여 모든 정점에 도달하는지 확인하고, 내부 간선 수가 정점 수보다 하나 작은지도 확인한다. 시간 복잡도는 $O(N^2(N+M))$이고 공간 복잡도는 $O(N+M)$이다.

전체 제한에서는 왼쪽 끝 $L$을 고정하고 오른쪽 끝 $R$을 늘리며 DSU로 연결 성분을 관리한다. 새 정점 $R$을 추가한 뒤, $L \le u < R$인 이웃 $u$와의 간선을 추가한다. 같은 연결 성분 안의 간선을 추가하게 되면 사이클이 생긴다. 이후 을 늘려도 이 사이클은 사라지지 않으므로 해당 의 탐색을 끝낸다. 사이클이 없는 상태에서 연결 성분이 하나라면 정답에 을 더한다. 연결되어 있지 않더라도 나중에 추가되는 정점이 성분을 이어줄 수 있으므로 탐색을 계속해야 한다.

각 정점에는 자신보다 번호가 작은 이웃만 내림차순으로 저장한다. 이웃 번호가 $L$보다 작아지는 즉시 순회를 끝내야 한다. 고정된 $L$에 대해 성공하는 합치기는 최대 $N-L$번이고, 실패하는 합치기는 최대 한 번이다. 정점 순회와 DSU 초기화를 합쳐 전체 시간 복잡도는 $O(M\log N + N^2\alpha(N))$, 공간 복잡도는 이다.

정답은 최대 $N(N+1)/2=50\,005\,000$이다. DSU 크기는 최대 $10\,000$, 간선 수는 최대 $1\,000\,000$이므로 모든 계산은 부호 있는 비트 정수 범위 안에 있다.

Solution written by GPT6