-
Top Tree & Maintaining Subtree Info In Link Cut Tree카테고리 없음 2021. 1. 24. 23:03
관련 문제
테스트 케이스는 모두 동일한 것으로 보인다.
Link Cut Tree는 트리를 동적으로 관리하기 위한 자료구조이지만 Path가 동적으로 바뀌면서 갱신되는 Auxiliary tree에는 기존 트리의 정보가 아닌 Access 이후의 경로에 대한 정보만 담겨있으므로 기본적으로 서브트리 쿼리는 다룰 수 없다. 오일러 투어 트리의 경우는 서브 트리 쿼리를 다룰 수 있지만 경로 쿼리는 처리할 수 없다.
물론 이를 개선해 동적으로 트리를 관리하면서 경로 쿼리와 서브트리 쿼리를 모두 처리할 수 있는 Topology Tree, Top Tree와 같은 자료구조가 있지만 구현이 까다로워 Competitive programming에는 적합하지 않고, 동적으로 서브트리를 관리하는 문제인 Codeforces Round #564의 Div1 E번에서는 Link Cut Tree에 트릭을 적용해 서브트리를 다루는 게 정해인 문제가 출제되었었다.
관련 글
- codeforces.com/blog/entry/80145
- codeforces.com/blog/entry/67511
- blog.csdn.net/weixin_30755393/article/details/94933503
- www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf
- pan.baidu.com/s/1kToUhJD (바이두링크 주의)