TopcoderSRM679 Div1 250 FiringEmployees(树形dp)
程序员文章站
2022-05-07 16:43:29
题意 ~~[题目链接]~~这怎么发链接啊。。。。。 有一个 $n$ 个点的树,每个点有点权(点权可能为负) ,求包含点$1$的最 大权连通子图(的权值和) 。 $n \leqslant 2500$ Sol 刚开始还以为是个树形依赖背包呢。。结果发现后面给的两个vector根本就没用 直接减一下得到每 ......
题意
[题目链接]这怎么发链接啊。。。。。
有一个 \(n\) 个点的树,每个点有点权(点权可能为负) ,求包含点\(1\)的最
大权连通子图(的权值和) 。
\(n \leqslant 2500\)
sol
刚开始还以为是个树形依赖背包呢。。结果发现后面给的两个vector根本就没用
直接减一下得到每个点的点权,然后xjb dp一波
#include<bits/stdc++.h> using 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<int> 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 <int> fa, vector <int> salary, vector <int> 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<int> 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); } /* 6 0 0 1 1 2 2 1 1 1 2 2 2 2 2 2 1 1 1 9 0 1 2 1 2 3 4 2 3 5 3 6 8 4 2 4 6 7 2 5 7 8 5 3 5 7 9 2 0 1 1 10 5 5 4 {{0, 1, 2, 3} {4, 3, 2, 1} {2, 3, 4, 5}} */