gifts.cpp

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

struct Tree {
        int value;
        Tree(int v) : value(v) {}
        vector<Tree*> c;
};


void print(Tree* t, int depth = 0) {
        for (int i = 0; i < depth; ++i)
                cout << '\t';
        cout << t->value << endl;
        for (Tree* c : t->c) {
                print(c, depth + 1);
        }
}

Tree* gen_tree(vector<int>& v) {
        Tree* root = NULL;
        unordered_map<int, Tree*> nodes;
        for (int i = 0; i < v.size(); ++i) {
                int ind = i + 1;
                if (v[i] == 0) {
                        root = new Tree(1);
                        nodes[ind] = root;
                } else {
                        auto node = new Tree(ind);
                        auto parent = nodes[v[i]];
                        parent->c.push_back(node);
                        nodes[ind] = node;
                }
        }
        //print(root);
        return root;
}

typedef std::pair<int, int> Ret;




unordered_map<int, vector<Ret>> cache;


Ret from_cache(Tree* t, int ban) {
        vector<Ret>& rets(cache[t->value]);
        for (Ret ret : rets) {
                if (ret.second != ban)
                        return ret;
        }
        throw runtime_error("???");
}


Ret solve(Tree* t, int ban_gift = 0) {
//      cout << "solve node: " << t->value << " ban_gift:" << ban_gift << endl;
        if (t->c.empty()) {
                if (ban_gift == 1) {
                        return Ret(2, 2);
                } else
                        return Ret(1, 1);
        }
        if (cache.find(t->value) != cache.end()) {
                //cout << "cache hit!" << endl;
                return from_cache(t, ban_gift);
        }
        int gift = 1;
        int min_sum = -1;
        int min_gift = -1;
        int max_c_gift = 1;
        vector<Ret> rets;
        do {
                int sum = gift;
                for (auto c : t->c) {
                        auto ret = solve(c, gift);
                        sum += ret.first;
                        max_c_gift = max(max_c_gift, ret.second);
                }
                if (min_sum == -1 || sum < min_sum) {
                        min_sum = sum;
                        min_gift = gift;
                }
                rets.push_back(Ret(sum, gift));
                ++gift;
        } while (gift <= max_c_gift + 1);
        sort(rets.begin(), rets.end());
        cache[t->value] = rets;
        return from_cache(t, ban_gift);
}


int main(int c, char* argv[]) {
        int t;
        cin >> t;
        for (int i = 0; i < t; ++i) {
                int n;
                cin >> n;
                vector<int> v;
                for (int k = 0; k < n; ++k) {
                        int l;
                        cin >> l;
                        v.push_back(l);
                }

                Tree* t = gen_tree(v);
                cache.clear();
                auto ret = solve(t);
                /*auto rets = cache[1];
                for (auto r : rets) {
                        cout << "sum: " << r.first << " CEO gift:" << r.second << endl;
                }*/
                cout << "Case #" << (i+1) << ": " << ret.first << endl;
        }
}