[일반] 백준 13309번 문제에 대한 질?문

[익명(61.74)]

https://www.acmicpc.net/problem/13309

KOI 2016 고등 3번 문제입니다.
이 문제 풀이들이 전부 다 Heavy-Light Decomposition을 이용하는데, 트리(중) 문제처럼 union-find만으로는 풀 수 없는 건가요?

쿼리 뒤집어서 수행하려고 생각을 많이 해봤는데 답이 안 나오더라고요...

...이참에 HLD를 익히는게 좋겠죠?

[저런...(hulahula3247)]

N <= 1000인데 브루트포스 돌려야지

[익명(61.74)]

헉 ㅋㅋㅋㅋㅋㅋㅋㅋ 이상한 실버 문제를 잘못 올렸네요 수정했습니다

[캐티(tae826)]

중트리 처럼은 안 풀리는데 HLD도 안 써도 됨. 되게 다양한 풀이가 있으니 한 번 생각해보는게

[익명(61.74)]

HLD 안 쓰고 큐 두개 써서 풀었습니다... 감사합니다!

[익명(121.169)]

내가 아는것중엔 HLD 안쓰고 오일러투어 테크닉이랑 레이지세그 조합해서 푸는는 방법이 있음. 좀더 나가면 레이지세그도 안쓰고 그냥 세그로도 풀수있고. 근데 hld는 익혀두는게 좋긴 할듯

[익명(61.74)]

감사합니다!