저는 세그먼트 트리를 활용해 각 정점마다 인접한 노드 개수, 방문할 수 있는 노드 중 번호가 가장 작은 노드를 저장했습니다.

노드를 방문하면 인접한 노드들을 모두 Update 시켜주는 방법으로 dfs를 돌렸습니다. 중간 값은 파라메트릭 서치로 찾았습니다.

분명 맞는 것 같은데 시간초과가 떠서 입출력을 빠르게 바꿔보았습니다. (기존에는 ios::sync_with_stdio(0); cin.tie(0);을 사용) 근데 바로 AC가 뜨더라구요.

Fast I/O 구현 코드

막히신 분들 fastio로 바꿔서 제출해보세요.