大神的世界

題目提示非常明顯，直接告訴你用 tree 就對了

tree 的每一個節點，都是一顆行星

每個行星儲存四個資訊

1. 自己的編號

2. child 數

3. 到 leave 的最長和次長距離

4. parent

則整棵 tree 任兩節點的最長距離，即為 root 的最長和次長相加

下面我採用 AOE 的寫法

以樹的角度來說就是 bottom-up ，由 leave 往上走，直到 root

#include <iostream>
#include <queue>

using namespace std;

typedef struct node
{
    int id;
    int child_num = 0;
    int max[2] = {};
    struct node *parent = nullptr;
}NODE;

constexpr int MAX_PLANET_NUM = 10000;

int main()
{
    NODE planet[MAX_PLANET_NUM];

    for(int i = 0; i<MAX_PLANET_NUM; i+=1)
        planet[i].id = i;

    int planet_num;
    while(cin >> planet_num){
        for(int i = 0; i<planet_num; i+=1){
            int sub_planet;
            while(cin >> sub_planet && sub_planet != -1){
                planet[sub_planet].parent = &planet[i];
                planet[i].child_num += 1;
            }
        }

        queue<int> leave;
        for(int i = 0; i<planet_num; i+=1)
            if(!planet[i].child_num)
                leave.push(i);

        while(!leave.empty()){
            int l = leave.front(); leave.pop();

            if(l == 0) break;

            NODE *lp = planet[l].parent;

            int step = planet[l].max[0] + 1;
            if(step > lp->max[0]){
                lp->max[1] = lp->max[0];
                lp->max[0] = step;
            }
            else if(step > lp->max[1])
                lp->max[1] = step;

            lp->child_num -= 1;
            if(!(lp->child_num))
                leave.push(lp->id);

            planet[l].max[0] = planet[l].max[1] = 0;
            planet[l].parent = nullptr;
        }

        cout << planet[0].max[0] + planet[0].max[1] << endl;
        planet[0].max[0] = planet[0].max[1] = 0;
    }

    return 0;
}