天下一プログラマーコンテスト2016A B問題

この問題を解きました。

tenka1-2016-quala.contest.atcoder.jp

問題設定がややこい感じもしますが、解法を思いつくのはそんなに難しくない気がします、ただ実装が大変だった。

答えはこちら

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring> 
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define pai 3.14159265359
    #define mod 1000000007
     
    bool ischecked[1001];
    vector<vector<int> > childleaf(1001), children(1001);
    int c[1001];
     
    vector<int> getchildleaf(int n)
    {
        if(ischecked[n]) return childleaf[n];
        ischecked[n] = true;
        vector<int> result;
        if(children[n].size() == 0){
            result.push_back(n);
        } else {
            for(int i = 0; i < children[n].size(); i++){
                vector<int> tmp = getchildleaf(children[n][i]);
                result.insert(result.end(), tmp.begin(), tmp.end());
            }
        }
        childleaf[n] = result;
        return childleaf[n];
    }
     
    int getminc(int n)
    {
        if(children[n].size() == 0) return c[n];
        int result = 100001;
        for(int i = 0; i < children[n].size(); i++){
            result = min(result, getminc(children[n][i]));
        }
        return result;
    }
     
    int solve(int n)
    {
        long long int nowans = 0;
        for(int i = 0; i < children[n].size(); i++){
            int nowchild = children[n][i];
            int nowc = c[nowchild];
            if(nowc != -1){
                nowans += nowc;
            } else {
                nowc = getminc(nowchild);
                // cout << nowchild << " " << nowc << endl;
                nowans += nowc;
                for(int j = 0; j < childleaf[nowchild].size(); j++){
                    c[childleaf[nowchild][j]] -= nowc;
                }
                nowans += solve(nowchild);
            }
     
        }
        return nowans;
    }
     
    int main()
    {
        int n, m;
        cin >> n >> m;
        ischecked[0] = false;
        for(int i = 1; i < n; i++){
            ischecked[i] = false;
            c[i] = -1;
            int p;
            cin >> p;
            children[p].push_back(i);
        }
        for(int i = 0; i < m; i++){
            int b, cinput;
            cin >> b >> cinput;
            c[b] = cinput;
        }
        getchildleaf(0);
        // for(int i = 0; i < n; i++){
        //     cout << i << ": ";
        //     for(int j = 0; j < childleaf[i].size(); j++){
        //         cout << childleaf[i][j] << " ";
        //     }
        //     cout << endl;
        // }
        cout << solve(0) << endl;
        return 0;
    }

0から順に、そのノードの子のそれぞれに対して、下につながっている葉のうちもっとも小さな値mincを選びます。それをそのノードと子の枝の重みにします。最後に下につながっている葉のCの値をminc分除いておきます。これを繰り返せば答えが出ます。
説明しづらい。

なんどもCを更新しているからTLEするかなと思いましたが、ノード数が少なかったからか大丈夫だったみたいです。