구간 안의 정점과 그 사이의 모든 간선으로 이루어진 유도 부분 그래프를 생각하자.
모든 학생에게 불씨가 도달하려면 이 그래프가 연결되어 있어야 한다. 연결된 그래프에 사이클이 있으면, 시작점에서 사이클에 도달한 불씨가 사이클을 계속 돌 수 있으므로 전달이 끝나지 않는다. 반대로 트리에서는 각 정점까지의 유일한 경로를 따라 불씨가 전달된다. 이때 마지막 전달 시각은 최대 이므로 시간 조건도 만족한다. 따라서 유도 부분 그래프가 트리인 구간의 수를 세면 된다.
작은 입력에서는 모든 구간을 직접 확인할 수 있다. 각 구간에서 BFS를 실행하여 모든 정점에 도달하는지 확인하고, 내부 간선 수가 정점 수보다 하나 작은지도 확인한다. 시간 복잡도는 이고 공간 복잡도는 이다.
전체 제한에서는 왼쪽 끝 을 고정하고 오른쪽 끝 을 늘리며 DSU로 연결 성분을 관리한다. 새 정점 을 추가한 뒤, 인 이웃 와의 간선을 추가한다. 같은 연결 성분 안의 간선을 추가하게 되면 사이클이 생긴다. 이후 을 늘려도 이 사이클은 사라지지 않으므로 해당 의 탐색을 끝낸다. 사이클이 없는 상태에서 연결 성분이 하나라면 정답에 을 더한다. 연결되어 있지 않더라도 나중에 추가되는 정점이 성분을 이어줄 수 있으므로 탐색을 계속해야 한다.
각 정점에는 자신보다 번호가 작은 이웃만 내림차순으로 저장한다. 이웃 번호가 보다 작아지는 즉시 순회를 끝내야 한다. 고정된 에 대해 성공하는 합치기는 최대 번이고, 실패하는 합치기는 최대 한 번이다. 정점 순회와 DSU 초기화를 합쳐 전체 시간 복잡도는 , 공간 복잡도는 이다.
정답은 최대 이다. DSU 크기는 최대 , 간선 수는 최대 이므로 모든 계산은 부호 있는 비트 정수 범위 안에 있다.
Solution written by GPT6
