[Link Cut Tree] 6. 간선 쿼리 앞에서는 정점의 쿼리에 대해서 다루었는데, 이제는 간선의 쿼리를 다룹니다.간선의 쿼리를 하는 방법은 2가지가 있습니다. 1) 자주 사용하는 방법으로, 간선의 값을 그 간선 중 자식 노드의 값으로 저장합니다.점 $x$와 $y$ 사이의 쿼리를 구할 때, $lca(x, y)$의 값은 포함되지 않음에 주의합시다. int query(node * x, node * y) { node * p = lca(y, x); int sum = 0; access(x); splay(p); if (p->r) sum += p->r->sum; access(y); splay(p); if (p->r) sum += p->r->sum; return sum; } 이 방법의 결정적인 단점은 루트를 바꿀 수 없다는 것입니다.Link/Cut Tree는.. 더보기 이전 1 ··· 12 13 14 15 16 17 18 ··· 24 다음