TopcoderSRM679Div1250FiringEmployees(树形dp)

题意

[题目链接]这怎么发链接啊。。。。。

有一个 (n) 个点的树，每个点有点权（点权可能为负） ，求包含点(1)的最
大权连通子图（的权值和） 。
(n leqslant 2500)

Sol

刚开始还以为是个树形依赖背包呢。。结果发现后面给的两个vector根本就没用

直接减一下得到每个点的点权，然后xjb dp一波

#includeusing namespace std;const int MAXN = 1e5 + 10;inline int read() {    char c = getchar(); int x = 0, f = 1;    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();    return x * f;}int a[MAXN], f[MAXN];vector v[MAXN];class FiringEmployees{public:    void dfs(int x, int fa) {        f[x] = a[x];        for(int i = 0, to; i < v[x].size(); i++) {            if((to = v[x][i]) == fa) continue;            dfs(to, x);            f[x] = max(f[x], f[x] + f[to]);        }    }    int fire(vector  fa, vector  salary, vector  productivity) {        int N = fa.size();        for(int i = 1; i <= N; i++) {            a[i] = productivity[i - 1] - salary[i - 1];            //cout << fa[i - 1] << endl;            v[fa[i - 1]].push_back(i);        }        dfs(0, -1);        return f[0];    }};int main() {    int N = read();    vector a, b, c;    for(int i = 1; i <= N; i++) a.push_back(read());    for(int i = 1; i <= N; i++) b.push_back(read());    for(int i = 1; i <= N; i++) c.push_back(read());    cout << FiringEmployees().fire(a, b, c);}/*60 0 1 1 2 21 1 1 2 2 22 2 2 1 1 190 1 2 1 2 3 4 2 35 3 6 8 4 2 4 6 72 5 7 8 5 3 5 7 920 11 105 54{{0, 1, 2, 3}{4, 3, 2, 1}{2, 3, 4, 5}}*/