나무 사슬 분할 원리

나무 사슬 을 한 마디 로 요약 하면 한 그루 의 나 무 를 여러 개의 사슬 로 나 눈 다음 에 데이터 구조 (나무 모양 배열, SBT, Splay, 선분 나무 등) 를 이용 하여 모든 것 을 유지 하 는 것 이다.
체인, 복잡 도 O (logn)
 
 
그렇다면 나무 사슬 을 나 누 는 첫 단 계 는 당연히 나 무 를 경중 변 으로 나 누 는 것 이다.
size (x) 를 x 를 뿌리 로 하 는 서브 트 리 노드 의 개수 로 정의 하고 v 를 u 로 하 는 아들 중 size 값 이 가장 큰 노드 로 정의 합 니 다. 그러면 (u, v) 는 무 거 운 변 이 고 나머지 는 가 벼 운 변 입 니 다.
 
물론 이것 에 관 해 서 는 두 가지 중요 한 성질 이 있다.
(1) 경 변 (u, v) 중 size (v) < = size (u / 2)
(2) 뿌리 에서 특정한 경로 까지 logn 의 가 벼 운 변 을 초과 하지 않 고 logn 의 무 거 운 경 로 를 초과 하지 않 습 니 다.
 
 
물론 분할 과정 은 두 번 dfs 또는 bfs 로 나 눌 수 있 습 니 다.
 
두 번 dfs 라면 첫 번 째 dfs 는 무 거 운 쪽 을 찾 는 것 입 니 다. 즉, 모든 무 거 운 쪽 을 기록 하 는 것 입 니 다.
그 다음 에 두 번 째 dfs 는 중 변 을 연결 하여 중 사슬 을 형성 하 는 것 이다. 구체 적 인 과정 은 바로 뿌리 노드 를 기점 으로 중 변 을 따라 아래로 확대 하고 중 사슬 로 당 겨 현재 중 사슬 에 있 는 절 이 아니다.
점, 모두 이 노드 를 기점 으로 아래로 다시 체인 을 당 깁 니 다.
 
 
분할 이 끝 난 후에 모든 무 거 운 체인 은 한 구간 에 해당 하 는 다음 에 데이터 구조 로 유지 하고 모든 무 거 운 체인 의 머리 와 꼬리 를 연결 시 켜 데이터 구조 에 올 린 다음 에 전 체 를 유지 합 니 다.
 
여기 에는 물론 많은 배열 이 있 습 니 다. 지금 은 제 가 각각 그들의 역할 을 소개 하 겠 습 니 다.
 
siz [] 배열, x 를 뿌리 로 하 는 하위 트 리 노드 개 수 를 저장 합 니 다.
top [] 배열, 현재 노드 가 있 는 체인 의 맨 위 노드 를 저장 합 니 다.
아들
dep [] 배열, 현재 노드 의 깊이 를 저장 합 니 다.
fa [] 배열, 현재 노드 를 저장 하 는 아버지
tid [] 배열, 트 리 의 각 노드 분할 후의 새로운 번 호 를 저장 합 니 다.
rank [] 배열, 현재 노드 가 선분 트 리 에 있 는 위 치 를 저장 합 니 다.
 
그러면 우 리 는 지금 설명 에 따라 분할 코드 를 제시 할 수 있다.
첫 dfs: 모든 무 거 운 변 을 기록 합 니 다.

void dfs1(int u,int father,int d)
{
    dep[u]=d;
    fa[u]=father;
    siz[u]=1;
    for(int i=head[u];~i;i=next[i])
    {
        int v=to[i];
        if(v!=father)
        {
            dfs1(v,u,d+1);
            siz[u]+=siz[v];
            if(son[u]==-1||siz[v]>siz[son[u]])
                son[u]=v;
        }
    }
}

두 번 째 dfs: 무 거 운 변 을 연결 하여 무 거 운 체인 을 만 듭 니 다.

void dfs2(int u,int tp)
{
    top[u]=tp;
    tid[u]=++tim;
    rank[tid[u]]=u;
    if(son[u]==-1) return;
    dfs2(son[u],tp);
    for(int i=head[u];~i;i=next[i])
    {
        int v=to[i];
        if(v!=son[u]&&v!=fa[u])
            dfs2(v,v);
    }
}

물론 문제 가 때때로 요구 변 이 많 기 때문에 2 차원 배열 로 변 을 표시 하지 않 고 인접 표 나 체인 식 전방 향 성 을 응용 하 는 것 이 좋다.
 
 
물론 이 안에 중요 한 조작 이 있 습 니 다. 그것 은 트 리 의 변 권 값 을 수정 하 는 것 입 니 다.
 
어떻게 u 에서 v 까지 의 변 권 의 값 을 수정 합 니까?여기에 두 가지 상황 이 있다.
(1) u 와 v 가 같은 체인 에 있 으 면 바로 수정 합 니 다.
(2) 만약 에 u 와 v 가 같은 체인 에 있 지 않 으 면 수정 하면 서 u 와 v 를 같은 체인 에 기대 면 첫 번 째 상황 이 된다.
 
그렇다면 현재 의 관건 은 u 와 v 를 어떻게 같은 체인 에 기대 느 냐 하 는 것 이다.이 문 제 는 여기에서 생략 하 겠 습 니 다.
 
이로써 나무 사슬 분할 원리 에 대한 기본 분석 이 완료 되 었 습 니 다!