using System using System Collections Generic using System Linq using

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication9
{
class AncientTree
{
List<int> p = null;
List<int> h = null;
List<int> weight = null;
List<int> sumWeightUp = null;
public AncientTree(int[] p, int[] w)
{
if (p.Length != w.Length)
{
throw new Exception();
}
int n = p.Length;
this.p = new List<int>(p);
this.weight = new List<int>(w);
this.h = new List<int>(n);
this.sumWeightUp = new List<int>(n);
for (int i = 0; i < n; ++i)
{
h.Add(-1);
sumWeightUp.Add(-1);
}
Action<int> precalc = null;
precalc = (int v) =>
{
if (h[v] >= 0) return;
if (p[v] == -1)
{
h[v] = 0;
sumWeightUp[v] = w[v];
}
else
{
precalc(p[v]);
h[v] = h[p[v]] + 1;
sumWeightUp[v] = sumWeightUp[p[v]] + w[v];
}
};
for (int i = 0; i < n; ++i)
precalc(i);
precalc = null;
}
public void Add(int p, int weight)
{
int v = this.p.Count;
this.p.Add(p);
this.weight.Add(weight);
int sumUp = weight;
int h = 0;
if (p != -1)
{
sumUp += this.h[p] + 1;
sumUp += sumWeightUp[p];
}
sumWeightUp.Add(sumUp);
this.h.Add(h);
}
public int getH(int v)
{
return h[v];
}
public int getW(int v)
{
return weight[v];
}
public int getP(int v)
{
return p[v];
}
public int getWeightUp(int v)
{
return sumWeightUp[v];
}
public void print()
{
Console.WriteLine("P\tH\tW\tSumW");
for (int i = 0; i < p.Count; ++i)
Console.WriteLine("{0}\t{1}\t{2}\t{3}", p[i], h[i], weight[i], sumWeightUp[i]);
}
}
class Program
{
static void Main(string[] args)
{
int[] p = { 1, -1, 1, 1, 2, 3, 0, 0 };
int[] w = { 4, 5, 8, 74, 45, 1, 2, 5 };
AncientTree tr = new AncientTree(p, w);
tr.Add(5, 15);
tr.print();
}
}
}