読者です 読者をやめる 読者になる 読者になる

紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

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];
}