Heavy Light Zersetzungs Ausgabe

Question

Ich studiere über HLD und ich fand heraus, dass ich 4 Dinge:

• Bei einem Knoten, kennen seine Kette;
• Gegeben ein Knoten, wissen Sie seine Position in seiner Kette;
• Angesichts einer Kette, kennen den Kopf davon;
• Gegeben eine Kette, die Länge davon kennen.

Ich konnte 3 dieser 4 Dinge tun, aber ich konnte nicht die zweite tun.

Ich habe es mit einem einzigen dfs auf dem Baum, und Ich würde gerne wissen, ob (und wie) es ist möglich, in meinem Code etwas hinzuzufügen, um das zweite Problem zu lösen. Hier

ist der Code:

#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; 
} 

Was macht es? Es ist ein einfaches dfs, du beginnst mit Kette 0 und folgst den ganzen Weg den Baum hinunter, ohne die aktuelle Kette zu ändern. Wenn Sie zu einem Blattknoten gelangen, ordnen Sie zu, dass dieser Knoten das letzte Element der aktuellen Kette ist (und die Größe der aktuellen Kette um 1 erhöht) und zum vorherigen Knoten zurückkehrt. Wenn du zurückkommst, siehst du die anderen Kinder des Knotens und übergibst ihnen jede eine andere Kette, und nachdem sie von allen zurückgekommen sind, wird die Kette des Sohnes mit der größten Größe zwischen allen zur Kette des aktuellen Knotens und dann es kehrt zurück.

Answer 1

Ein Ansatz, die Entfernung zum Ende der Kette zu speichern Code, indem zu kurz vor der Rückkehr Aussagen:

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

Nach der Tiefensuche abgeschlossen ist, sind Sie dann in der Lage, die Position zu berechnen in der Kette von etwas wie: