BOJ 28134 - 너의 집에 가까워졌어 너의 이름을 크게 불러봐도 너는 너무 멀어

BOJ 28134 - 너의 집에 가까워졌어 너의 이름을 크게 불러봐도 너는 너무 멀어

싸이클 $C$를 찾았다고 하자.

싸이클에서 구간합 배열을 이용하는 테크닉을 사용한다.

이 문제는 스위핑 + DP에 가까운거같기도

싸이클이 위와 같을 때, 다음과 같은 값들을 전처리해둔다.

1. 각 싸이클내부의 정점에서 자신의 싸이클에 포함되지 않은 노드들로 구성된 서브트리의 크기
2. 각 싸이클내부의 정점에서 자신의 싸이클에 포함되지 않은 노드들로 구성된 서브트리들의 정점에서 자신까지의 경로의 합
3. 각 싸이클내부의 정점에서 자신의 싸이클에 포함되지 않은 노드들로 구성된 서브트리들 안에서의 모든 경로들의 길이의 합

모두 $O(n)$으로 구해줄수 있다.

처음엔 이렇게 이어져있다고 하자.

$L$의 시작은 $0$이고, $R$의 시작은 $4$라고 하자.

$0$이 루트가 되도록 저 위에 세개들을 잘 구해준다음, 그걸 정답에 갱신하면 $\overline{0-4}$ 간선이 없는채로 정답을 하나 구한 셈이다.

이제 $L, R$ 을 각각 하나씩 줄여주고 늘려준다.

$L, R$에 대해서는 $1,2$를 관리해준다.

이제 $\overline{3-4}$가 끊어진 상태를 확인할 것이다.

$L, R$의 $1,2$ 번 값들을 적절히 조절해주고, $\overline{0-4}$ 를 이었을 때라고 가정하고 임시 정답에 그만큼 더해주고 정답에 갱신한다.

이런식으로 모든 간선에 대해서 체크하면 된다.