경로 쿼리

트리에서 u와 v를 잇는 경로상의 엣지들 (또는 노드들) 에 대한 뭔가를 물어보는 쿼리이다.

가장 간단한 것은 경로의 길이를 묻는 문제이다. 경로상의 엣지들에 대해서 sum 쿼리를 요구하는 것과 똑같다.

경로 쿼리를 해결하는 가장 단순한 방법은, 그냥 무지성으로 HLD를 적용하는 것이다. 그냥 이걸로도 웬만하면 대충 다 통한다.

O(n)의 전처리를 거치면 임의의 두 점이 들어왔을때 O(logn)시간을 써서, O(logn)개의 구간으로 변환할수 있다.

각각의 구간들에 대해서 구간 쿼리에서 쓰던 테크닉들을 그냥 적용하면 된다. 한개의 구간을 처리하는데에 걸리는 시간에 구간의 갯수O(logn)을 곱하면 쿼리를 처리하는 시간복잡도가 나온다.

업데이트가 없는 쿼리에 대해서는, 스파스 테이블을 쓸수 있다.

u↔v 의 경로를, u↔lca(u,v) 와 lca(u,v)↔v로 나눠서 각각을 계산한다음에 합치는 것이다. 이렇게 나누면 각각의 경로는 k번째 부모노드 까지의 경로이다.

스파스 테이블로 2^i번째 부모노드까지의 경로에 대한 값을 계산해두면, O(logn)에 각각을 계산할수 있다.

이렇게 스파스테이블을 만들면, 이것으로 lca도 자연스럽게 같이 구할수 있다.

그래서, 전처리에 O(nlogn), 쿼리 하나당 O(logn)에 처리가 가능하다.

경로의 길이는 결국 경로 합 쿼리와 동일하다.

LCA를 이용해서 u↔v 의 경로를 u↔lca(u,v) 와 lca(u,v)↔v로 나누면, u↔lca(u,v)의 길이는 dist[u] - dist[lca] 가 된다. lca(u,v)↔v도 마찬가지.

결국 LCA만 구하면 나머지는 O(1)에 계산 가능.

전처리 O(n), 쿼리 O(logn)으로 LCA를 계산한다 치면, 총 시간 복잡도도 전처리 O(n), 쿼리 O(logn)이 된다.

합 쿼리 뿐만 아니라 역연산이 있는 쿼리에 모두 적용 가능하다.

원래 트리의 엣지들을 추가하면서 새로운 형태의 트리를 만든다.

현재 추가된 엣지의 가중치가, 새 트리에서는 노드에 매핑되어 저장된다. 그리고 그 노드가 지금 합쳐진 컴포넌트들의 LCA가 되도록 트리를 만드는 것이다.

엣지가 추가되면서 노드들이 연결되어서 컴포넌트들로 뭉쳐질것이다. 이 컴포넌트들은 각각의 트리로 표현될텐데, 그때의 루트 노드를 따로 저장해놓는다. 이제 (u,v)엣지를 추가한다면, 새 트리에서는 u와 v에 엣지를 연결하는 것이 아니라, u가 속한 컴포넌트의 루트노드와 v가 속한 컴포넌트의 루트노드를 연결해주게 된다. 이것도 그대로 연결하는 것이 아니라.. 새로운 노드 p를 하나 추가해서 그 노드가 u의 루트노드와 v의 루트노드의 공통 부모가 되게 한다. 이러면 p는 합쳐진 컴포넌트의 루트노드가 된다. 그리고 p에 현재 추가된 엣지의 가중치를 매핑시켜 저장한다

이렇게 트리를 다 만들고 나면, u와 v가 연결된 시점의 가중치는 u와 v의 LCA노드에 매핑된 값이 된다.

결국 원래 트리에서의 경로 최솟값 쿼리를, 새 트리에서의 LCA 쿼리로 처리할수 있다.

n개의 엣지를 dsu로 추가하면서 새 트리를 만드는데에는 O(n*α(n))이 걸린다.

암튼 총 시간 복잡도는 O(n*α(n) + Qlogn) 또는 O(n*α(V) + Q + nlogn) 이다

각 컴포넌트마다, 이 컴포넌트의 원소를 포함하는 쿼리의 번호들을 갖고 있는 집합을 만들어준다.

한 쿼리는 두개의 노드를 포함하므로, 동일한 번호를 갖는 컴포넌트는 두개이다

컴포넌트가 합쳐질때마다, 두 컴포넌트의 쿼리번호집합을 합치게 된다.

합치는 과정에서 동일한 쿼리번호가 양쪽 집합에 있었다면, 현재 추가된 엣지의 가중치가 그 쿼리의 해답이 된다.

두개의 쿼리번호 집합을 합치는 것을 small-to-large 방식으로 처리하면, 모든 쿼리번호집합이 합쳐질때까지 O(QlogQ)번의 연산으로 해결되게 된다.

총 시간복잡도는 O(E*α(V) + QlogQ)이다