[Link Cut Tree] 4. 쿼리
이번 글에서는 트리에서의 경로 합을 구해봅시다.일단 루트에서 노드 x까지의 쿼리를 구할 수 있다면, 두 노드 사이의 쿼리는 LCA를 이용해서 구할 수 있습니다.( query(x, y) = query(x, root) + query(y, root) - query(lca(x, y), root) - query(parent(lca(x, y)), root) ) struct node { node *l, *r, *p; int cnt, val, sum; node() : l(0), r(0), p(0), cnt(0), val(0), sum(0) {} };일단 노드에 값과 구간 합을 저장하는 변수 val과 sum을 만들었습니다. void update(node * x) { x->cnt = 1; x->sum = x->val; i..
더보기