using System using System Collections Generic using System Linq using

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)
        }
    }
}