Euler Tour Technique, ETT는 트리에 대해서 dfs ordering을 진행하는 것으로 트리를 마치 구간처럼 다룰 수 있게 해주는 유형의 알고리즘이다.
특성상 그 자체로서 유용하다기보다는 세그트리같은 Range Query를 처리하고자 기용하는 편이며, 추후 heavy-light decomposition 등에 이용된다.
개인적으로는 이렇게 특정 N개 알고리즘의 조합을 묻는 문제들이 티어가 좀 높게 책정되는 감이 있어서 날먹에 애용하고 있는데, 그 도중 꽤나 재미있는 아이디어가 보여서 간만에 포스팅해본다.
BOJ 15491 도시 정비
간단한 문제 설명.
N - 1 개의 노드로 구성된 MST에서 특정 노드를 제거하면, 트리가 1개 이상으로 쪼개질 수도 있다. 이렇게 쪼개진 각각의 트리들에서 "트리의 모든 노드의 가격의 최대" 를 계산해 전부 더하면 얻을 수 있는 매출이 된다.
한개의 노드를 제거하는 N가지 경우에 대해 각각의 매출을 계산해 최댓값을 계산하면 된다.
ett 알고리즘을 적용해 트리를 구간 형태로 변화시키면, 얼핏 보았을 때 세그트리 Range Maximum Query를 이용해 매출을 쉽게 O(logN)에 계산할 수 있을것 같아 보인다.
이 문제에서 조금 골치아픈 부분은 특정 노드가 삭제되면서 생겨나는 트리 중에는, 부모 노드와 떨어져 나가면서 생기는 트리가 있다는 것이고 이 구간에 대한 RMQ를 어떻게 하면 빠르게 쿼리할 수 있을까 라는 고민이다.
흥미로운 아이디어
ett의 정의를 생각해보자.
ett에서 [in[k],out[k]] 구간이 무엇을 의미했던가?
ett에서 해당 구간은 해당 노드를 루트로 하는 서브트리의 전 구간을 의미한다.
우리가 쿼리하고자 하는 구간은 해당 서브트리만을 제외한 일종의 여집합이라 생각할 수 있고, 여구간이라고 생각해봐도 무방할 것이다.
ett에서 in과 out배열에 각각 기록되는 값은 dfs ordering과 동일하기 때문에,
[0,N) 구간이거나 [1,N] 구간이다. 나는 [1,N] 구간을 사용하기에 이걸 기준으로 설명하겠다.
특정 구간 [s,e]를 제외하는 여구간은 [1,s) U (e,N] 임을 알 수 있고, 우리는 두번의 RMQ를 통해서 부모 노드와 분리되며 생기는 부분 트리에 대한 RMQ를 구할 수 있게 된다.
if(i != 1) now += max(query(1, in[i]-1), query(out[i]+1, N));여기서 추가로 주의할 점은 루트노드를 분리하는 경우 [1,1) 이므로 구간이 성립하지 않고, 따라서 이 부분에서는 해당 연산을 진행해서는 안된다는 것이다.
삭제되는 노드의 자식 노드에 대해서는, 해당 자식별로 RMQ를 진행 후 그 값을 더해주면 된다.
for(auto k : g[i]){
if(in[k] > in[i]) now += query(in[k],out[k]);
}삽입된 if문은 그래프 구성 과정에서 양방향 그래프로 만들어주기 때문에 부모 노드인지 자식 노드인지를 구분하는 if문이다. dfs ordering에 의해 부모 노드인 경우는 반드시 자기 자신보다 preorder 순회한 숫자가 작다.
첨언
시간이 굉장히 빡빡한 편이다.
if(i != 1) now += max(query(in[1], in[i]-1), query(out[i]+1, out[1]));소스코드에 대해서는 통과를 받을 수 있었으나, 위에 적었듯 1과 N을 사용하면 TLE를 받는다. 아마 미세한 캐시히트 수준의 차이로 TLE가 발생하지 않았나 싶다.
pragma ofast 등을 명시해서 문제를 해결해 줄 수 있다.
