이번에 HLD 짜봤음
https://www.acmicpc.net/source/share/3e14b91244d9412cade017257815d1a9
HLD가 로직이 제일 쉬운듯?
euler-tour 한 다음 sparse로 하는거 구현은 많은데 쿼리가 O(1)이라 쿼리 많은 문제에서 활용하면 될거 같고
binary lifting이용하는거는 timer이용해서 나중에 비교 간략하게 하게 할 수 는 있는데 좀 더러운 느낌이라 어차피 시간복잡도 같은데 걍 HLD 쓸 듯?
이렇게 생각하면 맞음?
hld가 거의 항상 제일 빠르고 쉬움
굳굳 ㄳㄳ
저게 저렇게도 되는구나 신기하네
LCA를 HLD로도 짤 수가 있다고? 근데 LCA2가 P5고 트쿼1이 P1이니까 오버킬인가
오버킬일 수는 있는데 구현이 쉬우면 그렇게 해도 되지 사실 HLD 티어가 높은 이유는 세그 박아서 로그 제곱이 뭐를 많이 해서 그런데 lca 구하는 것 같은 경우에는 그냥 체인만 따라가면 되서 더 간단함
흐르드만 쓰고 세그 안쓰면 티어 더 낮지 증명때문에 플레긴 할듯
O(1) LCA 도 있으니 한번 공부해봐
HLD가 제일 쉬운데 왠지 binary lifting으로 많이 짜게됨