#include #include #include #include //#include using std::vector; using std::queue; class Node; class Node { public: int key; Node *parent; vector children; Node() { this->parent = NULL; } void setParent(Node *theParent) { parent = theParent; parent->children.push_back(this); } }; int treeLevelCounter(vector &nodes, int rootIndex) { int levelCounter = 1; queue q; int popCount = 0; int childrenCount = nodes[rootIndex].children.size(); int grandChildrenCount = 0; for (int i = 0; i < childrenCount; i++) { q.push(nodes[rootIndex].children[i]); } while (!q.empty()) { if (popCount < childrenCount) { Node *n = q.front(); q.pop(); int i = n->children.size(); if (i != 0) { for (int j = 0; j < i; j++) { q.push(n->children[j]); } } grandChildrenCount = grandChildrenCount + i; popCount = popCount + 1; } else { popCount = 0; childrenCount = grandChildrenCount; grandChildrenCount = 0; levelCounter = levelCounter + 1; } } return levelCounter + 1; } int getHeight(vector &a) { vector nodes; nodes.resize(a.size()); int rootIndex = 0; for (size_t i = 0; i < a.size(); i++) { int parentIndex = a[i]; if (parentIndex == -1) { rootIndex = i; } else { nodes[i].setParent(&nodes[parentIndex]); } } return treeLevelCounter(nodes, rootIndex); } //TEST(GetTreeHeight, t1) { // vector a = {4, -1, 4, 1, 1}; // ASSERT_EQ(3, getHeight(a)); //} // //TEST(GetTreeHeight, t2) { // vector a = {-1, 0, 4, 0, 3}; // ASSERT_EQ(4, getHeight(a)); //} // //TEST(GetTreeHeight, t3) { // vector a = {9, 7, 5, 5, 2, 9, 9, 9, 2, -1}; // ASSERT_EQ(4, getHeight(a)); //} // //TEST(GetTreeHeight, t4) { // vector a = {8, 8, 5, 6, 7, 3, 1, 6, -1, 5}; // ASSERT_EQ(6, getHeight(a)); //} int main() { size_t an; std::cin >> an; vector a(an); for (size_t i = 0; i < an; i++) { std::cin >> a[i]; } std::cout << getHeight(a) << std::endl; }