using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
public class Parents
{
public int[] P;
public int[] W;
public int[] H;
private const int defaultCapacity = 10;
private int size;
public Parents(int max_n)
{
this.size = max_n;
this.P = new int[defaultCapacity];
this.W = new int[defaultCapacity];
this.H = new int[defaultCapacity];
for (int i = 0; i < defaultCapacity; ++i)
{
this.H[i] = -1;
}
}
public void Add(int newElement, int id)
{
this.size++;
P[this.size - 1] = id;
W[this.size - 1] = newElement;
}
public int GetLength(int id)
{
int count = 0;
while (this.P[id] != -1)
{
count++;
id = this.P[id];
}
return count;
}
public int GetFullLength()
{
int ret = 0;
for (int i = 0; i < this.size; ++i)
{
this.H[i] = GetLength(i);
ret += this.H[i];
}
return ret;
}
public void GetLength2(int id)
{
int first = id;
int count = 0;
while (this.H[id] == -1)
{
id = this.P[id];
count++;
}
count += this.H[id];
id = first;
while (this.H[id] == -1)
{
this.H[id] = count;
id = this.P[id];
count--;
}
}
public void GetFullLength2()
{
for (int i = 0; i < this.size; ++i)
{
GetLength2(i);
}
}
}
static void Main(string[] args)
{
int n = 8;
int[] input_p = { 1, -1, 1, 1, 2, 3, 0, 0 };
int[] input_w = { 7, 12, 11, 5, 4, 3, 7, 9 };
Parents M = new Parents(n);
for (int i = 0; i < n; ++i)
{
M.P[i] = input_p[i];
M.W[i] = input_w[i];
if (input_p[i] == -1)
{
M.H[i] = 0;
}
}
M.Add(15, 3);
M.GetFullLength2(); //O(n)
}
}
}