ABC026_C

※bukaという変数とkouhaiという変数が混ざって大変汚いコード
部下と上司の木を表現してある社員が部下を持たなければ1,
部下を持っていればその部下の中からmax(部下の給料)+min(部下の給料)+1を返す.
メモ化再起風に解いた.

#include <bits/stdc++.h>
using namespace std;
static const int MAX_N = 20;
 
struct Node{
    vector<Node*> kouhai; 
    int kyuuryou;
};
 
Node worker[MAX_N];
 
int solve(Node *p)
{
    /*
        引数(Node*) : 社員
        返り値(int)  : 給料 worker[num].kyuuryou
    */
    if((int)p->kouhai.size()==0){//部下がいなければ
        //給料を1にセットしてから給料1を返す
        p->kyuuryou = 1;
        return 1;
    }else{//部下がいれば
        //部下全員の給料を求めmax(部下の給料)+min(部下の給料)+1を返す
        vector<int> buka_kyuuryou;
        int max_kyuuryou = INT_MIN;
        int min_kyuuryou = INT_MAX;
        for(int i=0;i<(int)p->kouhai.size();i++){
            int tmp = solve(p->kouhai[i]);//部下p->kouhai[i]の給料
            buka_kyuuryou.push_back(tmp);
            max_kyuuryou = max(tmp,max_kyuuryou);
            min_kyuuryou = min(tmp,min_kyuuryou);
        }
        p->kyuuryou = max_kyuuryou+min_kyuuryou+1; 
        return p->kyuuryou;
    }
}
int main()
{
    int n,x;
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>x;
        worker[x-1].kouhai.push_back(&worker[i]);//社員iの先輩は社員x-1 == 社員x-1の後輩は社員i
    }
    solve(&worker[0]);
    int ans = worker[0].kyuuryou;
    cout<<ans<<endl;
    return 0;
}

より簡単な方法
部下が上司より後になるのを利用して後ろから計算していく.

int P[MAX_N];//給料
int minP[MAX_N];//部下の給料の最小値
int maxP[MAX_N];//部下の給料の最大値
int sub[MAX_N];//部下の人数

for(int i=N-1;i>=0;i--){
    if(sub[i].size()==0){//部下が0人ならば
        P[1]=1;//給料は1
        continue;
    }
    //部下がいるならば部下の中で最大+最小+1
    maxP[i] = 0;
    minP[i] = (int)1e9;
    for(int j=0;j<(sub[i].size();j++){
        maxP[i] = max(maxP[i],P[j]);
        minP[i] = min(minP[i],P[j]);
    }
    P[i] = maxP[i] + minP[i];
}