기여창에는 PBS 풀이가 있다고 종종 나와있는데 제출목록엔 도통 보이지 않네요..!!


PBS 풀이로 해결하신 분이 계시다면 / 감이 잡히시는 분이 계시다면

댓글로 알려주시면 감사드리겠습니다!!!

zenith82114   8달 전

각 정점마다 ON 또는 OFF 상태를 가진다고 합시다. 처음에 모든 정점이 OFF였다가 가중치가 커지는 순서대로 하나씩 ON으로 바뀌어가는 상황에서, "x~y 경로상에 ON인 정점이 몇 개인가"라는 형식의 질문에 실시간으로 답할 수 있다면 이 문제를 PBS로 풀 수 있습니다.

이미 아시겠지만 루트를 R이라 할 때 x~y는 R~x, R~y, R~lca(x,y), R~par(lca(x,y))를 조합하여 표현할 수 있습니다. 정점 x의 조상 중 ON인 것의 개수를 f(x)라고 하면 우리는 f(x)만 빠르게 수정하고 조회할 수 있으면 됩니다. 어떤 정점이 새롭게 ON으로 바뀌었을 때 f 값이 커져야 하는 정점들이 누구인지 생각해보시면 푸실 수 있을 것입니다.

댓글을 작성하려면 로그인해야 합니다.