문제 링크
- http://icpc.me/13518
사용 알고리즘
- Mo’s Algorithm
시간복잡도
- $O((N+Q) \sqrt N)$
풀이
쿼리만 보면 모스 알고리즘 느낌이 나는데, 트리라는 것이 짜증납니다.
트리에서 모스 알고리즘을 돌릴 방법을 생각해봅시다.
트리의 euler tour를 구해봅시다. 이때 각 정점에 들어가는 순간과 빠져나가는 순간을 각각 모두 봐야합니다.
빨간색 원은 in(들어가는 시간), 파란색 원은 out(나가는 시간)을 의미합니다.
트리에서 u에서 v로 가는 경로(u -> v)는 크게 두 가지 종류로 나눌 수 있습니다. 아래 두 가지 종류에 대해 각각 euler tour 상에서 어떤 형태인지 봅시다.
- u, v 중 한 정점이 u, v의 LCA이다.
- u, v 모두 LCA가 아니다.
설명의 편의를 위해 두 정점 중 dfs로 먼저 방문하는 정점을 u, 나중에 나오는 정점을 v라고 합시다.
1번의 경우를 그림으로 봅시다.
[in(u), in(v)] 구간을 보면, 경로 위에 있는 정점은 in값만 나오고 경로 위에 없는 정점은 in과 out이 모두 나오거나 아예 나오지 않습니다.
이것은 dfs 과정을 생각해보면 자명합니다. 그러므로 우리는 1번에 해당하는 경로를 처리할 때는 [in(u), in(v)] 구간을 봐주면 됩니다.
2번의 경우를 그림으로 봅시다.
[out(u), in(v)] 구간을 보면, 경로 위에 있는 정점은 in/out 중에서 하나만 나오고 경로 위에 없는 정점은 in과 out이 모두 나오거나 아예 나오지 않습니다.
단, u와 v의 LCA에 해당하는 정점은 경로 위에 있음에도 불구하고 in과 out이 모두 나오지 않습니다. 이 부분에서 예외처리를 해야 합니다.
이것도 dfs 과정을 생각해보면 자명합니다. 그러므로 우리는 2번에 해당하는 경로를 처리할 때는 [out(u), in(v)] 구간을 봐주고, 추가로 in(LCA)를 봐야 합니다.
경로에 대한 쿼리를 구간에 대한 쿼리로 바꿨다면, 모스 알고리즘을 이용해 쉽게 해결할 수 있습니다.