중공업 라이트 분해 문제

Question

나는 HLD에 대해 공부하고 난 4 일이 필요하다는 것을 발견 :

• 노드 감안할 때, 그 체인을 알고;
• 주어진 노드에서 체인의 위치를 ​​확인하십시오.
• 체인이 주어지면 그 머리를 알아보십시오.
• 체인이있는 경우 길이를 알아 두십시오.

나는이 4 가지 중 3 가지를 할 수 있었지만 두 번째 것은 할 수 없었다.

나는 나무에서 하나의 dfs를 사용하여 만들었으며 두 번째 문제를 해결하기 위해 내 코드에 뭔가를 추가 할 수 있는지 알고 싶습니다..

#define maxn 1010 

int SizeOf[maxn], SpecialChildOf[maxn], 
    ChainOf[maxn], SizeOfChain[maxn], HeadOfChain[maxn]; 
int chain = 0; 
vector<int> T[maxn]; 

void dfs(int u){ 
    SizeOf[u] = 1; 
    int adj = T[u].size(); 
    if(!adj){ 
     ChainOf[u] = chain; 
     SpecialChildOf[u] = -1; 
     HeadOfChain[chain] = u; 
     SizeOfChain[chain]++; 
     return; 
    } 
    dfs(T[u][0]); 
    int specialChild = T[u][0]; 
    SizeOf[u] += SizeOf[specialChild]; 

    for(int i = 1; i < adj; i++){ 
     int v = T[u][i]; 
     chain++; 
     dfs(v); 
     if(SizeOf[v] > SizeOf[specialChild]) specialChild = v; 
     SizeOf[u] += SizeOf[v]; 
    } 

    SpecialChildOf[u] = specialChild; 
    ChainOf[u] = ChainOf[specialChild]; 
    SizeOfChain[ChainOf[u]]++; 
    HeadOfChain[ChainOf[u]] = u; 
} 

는 무엇입니까 : 여기

코드인가? 그것은 단순한 dfs입니다. 체인 0부터 시작하여 현재 체인을 변경하지 않고 트리를 끝까지 따라갑니다. 잎 노드에 도달하면이 노드가 현재 체인의 마지막 요소이고 현재 체인의 크기가 1 씩 증가한다는 것을 지정하고 이전 노드로 돌아갑니다. 다시 돌아 오면 노드의 다른 자식을보고 서로 다른 체인을 전달하고 모두에서 돌아온 후에 가장 큰 크기의 아들 체인이 현재 노드의 체인이 된 다음 그것은 돌아온다.

Answer 1

한 가지 방법이 바로 반환 문 앞에 코드를 추가하여 체인의 끝에까지의 거리를 저장하는 것입니다 :

DistanceToEnd[u] = SizeOfChain[ChainOf[u]]; 

을 첫 번째 검색이 완료된 당신의 깊이 후에는 위치를 계산할 수 있습니다

distanceToStart = SizeOfChain[ChainOf[u]] - DistanceToEnd[u];