APL(NARS), 98 chars

r←d w;l;i;k i←1⋄l←≢w⋄p←0⋄r←⍬ →0×⍳i>l⋄→3×⍳i≤2⋄→3×⍳∼⍬≢k←⍸w[i]=w[1..i-1]⋄p←r[↑1⌽k] r,←p⋄i+←1⋄p+←1⋄→2 

//12+17+51+18=98

I have not much familiarity with this argument. this function it seems fits the data test... It would work that increment one counter p that represent deep that start from 0, but if the number has index >2 and in the array of input is already calculated the deep, than assign to p the deep already calculated and continue as above. For root the deep is 0, for all the nodes have parent root the deep is 1.

 d 0 0 d ,0 0 d 0 0 0 1 d 0 0 1 2 3 4 1 6 0 1 2 3 4 5 2 3 d 0 0 1 2 3 3 0 6 6 6 9 0 1 2 3 4 4 1 2 2 2 3 d 0 0 1 1 3 0 0 6 0 8 8 10 10 8 0 1 2 2 3 1 1 2 1 2 2 3 3 2