SRM 679 div1 easy: FiringEmployees

SRM 679 に参加しました。easy がめっちゃ簡単だったんですが英弱パワーを発揮して点数が低かったです。

問題

木構造になっている社員関係が与えられる。各社員 v は, productivity[v] - salary[v] だけの利益を挙げられる。

利益を最大化するために社員を首にすることを考えているが, 社員 v を首にした場合, v の以下の子はすべて首にしなければならない。この場合に利益は最大でいくらになるか。

解法

木 dp やるだけ。

vi G[3000];
vector<int> salary, productivity;

int dfs(int v, int p) {
    int ret = 0;
    if (v == 0) {
        for (int ch : G[v]) {
            ret += dfs(ch, v);
        }
        return ret;
    }
    int tmp = productivity[v-1] - salary[v-1];
    for (int ch : G[v]) {
        if (ch == p) continue;
        tmp += dfs(ch, v);
    }
    ret = max(ret, tmp);
    return ret;
}

class FiringEmployees {
public:
    int fire(vector <int> manager, vector <int> sala, vector <int> product) {
        int n = manager.size();
        salary = sala;
        productivity = product;
        for (int i = 0; i <= n; i++) G[i].clear();
        for (int i = 1; i <= n; i++) {
            G[manager[i-1]].push_back(i);
            G[i].push_back(manager[i-1]);
        }
        return dfs(0, -1);
    }
};