koi 2016 고등부 본선 트리 풀이

2016 고등부 본선 트리 풀이

온라인 저지 사이트인 jungol에서 채점해볼수 있다.http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2268&sca=60&s1=&s2=&s3=&s4=

 

나는 이 문제를 세그먼트 트리와 dfs로 풀었다.

먼저 LCA 알고리즘을 알고 있어야 이 문제를 풀 수 있다. ---추후 업데이트---

 Prob No.07F7 : Lowest Common Ancestor (LCA) [CH02.1.Algorithm(Exist#D)]                             

http://koistudy.net/?mid=prob_page&NO=2039


1) 전처리:
트리의 루트부터 DFS를 들어간다. 각 트리의 노드는  DFS를 들어갈 때의 값과 나올 때의 값 2가지를  가지고 있다.
LCA 전처리 + 넘버링

void DFS(int h,int from)
{
    int pos=pr[1][from],i;
    visit[from]=1;
    in[from]=++cnt; <-들어 갈때의 값
    pr[0][from]=from;
    lev[from]=h;
    for(i=2;i<=L;i++){
        pos=pr[i-1][pos];pr[i][from]=pos; // LCA
    }
    for(i=V[from].size()-1;i>=0;--i){
        if(visit[V[from][i]]==0){
            DFS(h+1,V[from][i]);
        }
    }
    out[from]=++cnt;-> 나올 때의 값.
}

어떤 노드 v에서 DFS 들어 갈 때의 값(in[v] ) , 나올 때의 값(out[v]) 라 하면 v의 부분트리에 있는 노드들의 들어갈 때와 나올 때의 값은 모두 in[v]와 out[v] 사이에 있다.

이 부분트리의 노드 u의 in[u],out[u]들은 연속되어 있으니까 뭔가 처리해주기에 매우 수월하다.
트리 관련 문제에서 매우 자주 쓰이는 트릭이다.

2) 노드와 노드 사이의 간선을 끊는 처리 :

루트의 깊이가 1이고 그 자식들이 2라고 편의상 가정 하자.
만약 A와 B를 끊을 때  A가 B의 조상이라하자.

 B의 자식들(B포함)은 최대로 올라갈수 있는 높이가 현재 B의 높이가 된다.
자식들이 최대로 올라 갈수 있는 높이을 세그먼트 트리 제한 해준다.

전처리에서 B의 자식들의 DFS 값들은 연속 되어 있다.
세그먼트 트리리에 [ in[B], out[B] ]이 속해 있는 모든 구간에 B의 깊이로 최댓값 갱신을 해준다. 시간 복잡도 : O(log n)
ex) (2~7)->(2)+(3~4)+(5~6)+(7) 구간에 해당하는 배열 값들을 최대값으로 갱신

3) 두 노드 A,B가 연결되어 있는지 보는 법

어떤 노드 v에서 최대한 올라갈 수 있는 값에 대한 제한을 세그먼트 트리로 확인한다.
X=max((세그 먼트트리에서 in[v]가 속해 있는 모든 구간)의 높이 제한)
그 최댓값이 X라면 그 노드에서 아무리 올라가 봤자 깊이 X까지 올라 갈수 있다는 것이다.
어떤 노드에서 깊이 X까지 올라가는 건 LCA로 O(log(n))만에 할 수 있다.

A의 최고 조상과 ,B의 최고 조상이 같다면 연결되어 있고, 조상이 같지 않으면 연결되어 있지 않다.

위 3가지의 처리를 이용한다면 두 노드가 연결되어 있는지 아닌지 알 수 있고 이 후 결과에 따라 간선을 끊어 줄 수 있다.
쿼리당 시간 복잡도 logn

전체 시간복잡도 : O( Q logn )