링크/컷 트리¶
링크/컷 트리(Link/cut tree)는 트리(또는 포레스트)의 구조가 동적으로 변할 때 경로 쿼리를 효율적으로 처리하는 자료구조입니다.
- solved.ac 티어: 다이아1
- 선행 지식: [[스플레이 트리]]
배우기¶
다음을 순서대로 읽고 풀면 됩니다.
- Link Cut Tree 1 by imeimi
- Link Cut Tree 2 by imeimi
- 문제: 트리와 쿼리 11
- Link Cut Tree 3 by imeimi
- 이제 스플레이 트리에서 했던 대로 각 노드에 "값"을 추가해 줍시다.
- Link Cut Tree 5 by imeimi
- 이제
makeRoot함수가 있으면 임의의 경로x-y를 쿼리할 수 있습니다.x를 루트로 만든 다음y를 access하면 됩니다. - 임의의 간선
x-y를 추가/제거할 수도 있습니다.x를 루트로 만든 다음y를 link/cut하면 됩니다. - 문제: 남극 탐험
- 문제: Dynamic Tree Vertex Add Path Sum
- 문제: Dynamic Tree Vertex Set Path Composite
- Link Cut Tree 6 by imeimi