Euler Tour Tree(ETT)

https://codeforces.com/blog/entry/18369

On Euler tour trees - Codeforces

이번에는 undirectd tree를 다루는 문제들에서 알아두면 좋은 Euler Tour Tree에 대해서 알아보도록

하겠습니다.

 

Euler Tour의 사전적 정의는 다음과같이 

"각 간선을 한번만 지나면서(양방향간선이라는 것을 유의하자) 그래프에 있는 모든 노드를 순회(traversal) "

하는 Tour를말하며 트리의 경우 DFS를 통해서 반드시 이런 Tour를 나타내는 배열을 얻을 수 있습니다.

 

입체적인 구조인 트리를 Euler Tour를 하게 되는 DFS를 통해

ETT[]={1,2,6,6,2,4,1,3,3,5,5}와 같이 순회한 노드로 이루어진 배열로 표현 할 수 있으며

(이 글에서는 '리스트'라고 표현 하겠습니다.)

트리를 "일렬로 쫙편다"고도 말할 수 있습니다.

즉, Euler Tour Tree 란 rooted undirected tree를 일차원 적인 배열(sequence)로 보는 방법론인것이죠.

 

 

그렇다면, 이렇게 Tree를 배열로 표현하는 방식에는 어떠한 이점이 있을까요??

그것은 트리에서 나타나는 임의의 쿼리를 

ETT[]에 대한 "구간의 쿼리"로 치환하여 접근할 수 있다는 점입니다.

즉, 구간 쿼리를 쉽게 처리할 수 있는 자료구조들(ex)새그먼트 트리, spase table을 이용한 전처리)등과 함께 이용하면

빠르게 처리하게 될 수 있다는 것이죠.

 

ETT[]배열을 나타내는 방식은 위 글에서는 주어진 문제에 조건에 따라 3가지로 나눠서 분류합니다.

(2번과 3번의 차이는 DFS로 배열을 만들어나갈때, 배열에 언제 집어넣을지에  따라서 달라집니다.)

1)  edge의 리스트로 나타내는 경우

Euler Tour를 하면서 지나는 간선들의 집합으로 배열을 나타내는 경우로써, Euler Tour의 정의에

해당하는 구현입니다. 여기서는 소개만 하고 넘어가겠습니다.

 

2)  vertex를 방문할때마다 리스트에 집어넣는 경우 ( 사용용도 : LCA)

방문할떄, 즉 부모로부터 호출받을 경우, 자식으로갔다가 다시 돌아올떄마다 리스트의 넣어주는 방식입니다.

void dfs(int u, int pu){
    euv[clk++] = u; // 부모로부터의 호출
    for(int v : adj[u]){
        if(v == pu)continue;
        dfs(v,u);
        euv[clk++] = u; //자식으로 갔다가 돌아올때
    }
}

이렇게 얻어진 리스트의 총 노드의 개수는 2n-1개이며, 이런 방식의 리스트를 이용하여 LCA(최소 공통 조상)문제를 

푸는데 어떤식으로 사용될 수 있을까요??

 

만약 2번노드와 5번노드의 최소공통 조상을 찾으라는 쿼리가 주어졌다고 합시다.

그렇다면 이는 "2번에서 5번까지 Tour를 하면서 지나간 노드중에 가장 깊이가 작은 노드"를 찾는

쿼리로 바꿔서 처리 할 수 있습니다.

그렇다면 여기서 2번 노드가 리스트에 2번째에서도 나오고 4번째에서도 나오는데 이중에서 어떤 것을 이용해야 하나??

하는 문제가 나올 수 있습니다.

정답은 어느 것을 이용하든 답에는 영향을 주지 않는다는 것입니다.

왜냐하면 어떤 노드의 첫번째 호출과 두번째 호출 사이에 지나는 모든 점들의 깊이는 DFS이므로 2번 노드보다 클 수 밖에 없고, 그렇기 때문에 구간에서의 최소를 구하는 것에 아무런 영향을 주지 않기 때문입니다.

(그림으로 그려서 여러번 해보면 좀 더 명확하게 얻을 수 있습니다.)

따라서 dfs로 tour list를 만들어 나가면서 

배열 f[u] = u가 list에 처음방문했을 때를 가리키는 index 를 저장시켜나가면됩니다.

void dfs(int u,int pu){
    d[u] = d[pu] + 1; // 노드 u의 
    f[u] = clk; // 노드 u가 euv list에서 어떤 인덱스에 있는지 저장
    euv[clk++] = u;
    for(int v : adj[u]){
        if(v==pu)continue;
        dfs(v,u);
        euv[clk++]=u;
    }
}
 

두 노드 u,v의 LCA를 구하는 쿼리를

리스트에서

u,v가 각각 처음들어간 시점(인덱스)사이에 있는 모든 노드들중 depth가 가장 작은 노드를 구하는

구간최소 (RMQ)쿼리로 바꿔서 처리할 수 있습니다. 

lca(u, v) = argmin(f(u), fi(v)) in depth 

이 RMQ를 새그먼트트리나 sparse table을 이용하여 처리하면 됩니다.

https://www.acmicpc.net/problem/11438

 

 

참고로 이런 방식의 ETT를 Rerooting하는 경우에서 이용한다고도 하는데 이에 대해서는 추후에 다뤄보도록 하겠습니다.

 

3) vertex를 방문할때랑 떠날떄 넣어주는 경우 (사용용도 : 서브트리의 합을 구할때)

void dfs(int u,int pu){
    d[u] = d[pu] + 1; // 노드 u의 
    f[u] = clk; // 노드 u가 euv list에서 어떤 인덱스에 있는지 저장
    euv[clk++] = u;
    for(int v : adj[u]){
        if(v==pu)continue;
        dfs(v,u);
    }
    euv[clk++]=u;
}

2번의 경우와 비교해서 자식에서 돌아올 떄 리스트에 추가해 주던 것을 정점을 떠날 때 넣어주는 점만 달라졌습니다.

그런데 이런 경우 리스트를 직접 관리해 줄 필요 없이, 

'노드를 처음 방문했을 떄의 리스트에서의 시점(인덱스)', '노드를 떠날떄의 리스트에서의 시점' 두개의 배열만 관리해주면 우리가 원하는 쿼리를 처리해 줄 수 있습니다.

// sn[] 노드를 처음 방문했을 때의 시점
// en[] 노드를 떠날 때의 시점
void dfs(int i) {
    sn[i] = ++clk;
    for (int V : vt[i]) {
        if (!sn[V])dfs(V);
    }
    en[i] = clk;
}

i	sn(i)	en(i)
1	1	5
2	2	4
3	3	3
4	4	4
5	5	5

dfs 순서상으로 1-2-3-4-5순으로 방문한다고 했을 때  위와 같이 이루어진 sn[] en[]  테이블을 얻을 수 있죠.

어떤 정점 u에서부터 dfs 방식으로 tour를 한다고했을때, 아직까지 가지 않은 자신과 연결된 모든 정점(tree이므로 자신과 연결된 자식노드들)을 전부 방문하고 (여기서는 리스트를 관리해주진 않기 때문에 리스트에 인덱스에 해당하는 clk를 늘려줍니다. )나서야 자기 자신으로 돌아옵니다. 따라서, 갈 수 있는 모든 노드를 다 거치고 en[u]에 인덱스에 해당하는 clk를 다시 집어넣습니다.

 

그렇다면 어떤 결과를 얻을 수 있을까요??

[sn[i],en[i]]까지의 정점들은 i에서부터 dfs로 갈수있는 모든 노드를 의미합니다.

즉 다시말해서 i를 루트로 하는 서브트리의 모든 정점의 리스트를 구간 [sn[i],en[i]]의 형태로 얻을 수 있죠.

따라서 임의의 정점을 루트로 하는 서브트리에 대한 연산, 임의의 정점과 그 자식들에 대해서 ~~를

수행하시오 하는 쿼리를 구간의 쿼리로 바꿔서 처리할 수 있습니다.

 

예를 들어 각 노드들의 가중치가 d[]배열에 주어지고

임의의 노드 i와 그 자식들의 가중치의 합을 구하는 쿼리가 주어지면

$$\sum_{i=sn[i]}^{en[i]} d[i]$$

즉, [sn[i],en[i]]에 대한 구간의 쿼리로 바꿔서 접근할 수 있는 것이죠.

 

 

따라서 이또한 마찬가지로 구간에 대한 처리를 용이하게 할 수 있는 자료구조인 새그먼트 트리를 이용하여 처리해주면됩니다.

 

이번엔 문제를 보면서 익혀보도록 합니다.

 

 

 

https://www.acmicpc.net/problem/2820

 

2820번: 자동차 공장

 

2개의 쿼리로 이루어져 있는데

1. p a x가 주어진 경우 a의 모든 부하의 월급을 x만큼 증가시킨다. (-10,000 ≤ x ≤ 10,000)
2. u a가 주어진 경우에는 a의 월급을 출력한다.

 

 

2번 쿼리 같은 경우 a에 해당하는 , 새그먼트 트리에서의 sn[i]에 해당하는 값을 출력하면 됩니다.

 

1번 쿼리는 어떤식으로 접근해아 할까요?

모든 부하라는 것은 자신을 루트로 하는 subtree에서 자기 자신만을 제외해주면 얻을 수 있고,

이를 구간 쿼리로 바꾸면 [sn[i]+1,en[i]]구간을 봐주면 되죠.

이 구간 쿼리에 대해서 구간을 한번에 update할 때 유용한 자료구조, 즉 lazy propagation을 이용해주면 됩니다.