树形DP
统计人数
一家公司里有 n 个员工，除了公司 CEO 外，每个人都有一个直接上司。我们想知道，每个人的团队（包括他/她自己、他的直接下属和间接下属）一共有多少人？
dfs：
用vector存入每个人的下属，用size数组表示每个人的下属数量，那么一个人的下属数量等于他的每个直接下属的数量，直接dfs即可。
int a[100001], size_[10001];
vector<int> sub[100001];
void solve(int i) {
size_[i] = 1;
for (auto it : sub[i]) {
solve(it);
size_[i] += size_[it];
}
}
int main() {
int n;
cin >> n;
for (int i = 2; i <= n; i++) {
cin >> a[i];
sub[a[i]].push_back(i);
}
solve(1);
for (int i = 1; i <= n; i++) cout << size_[i] << " ";
return 0;
}bfs
用vector存入每个人的下属，用size数组表示每个人的下属数量，那么一个人的下属数量等于他的每个直接下属的数量
在计算每一个人的下属数量时，我们要预先知道他的直接下属的团队数量，所以要先从 CEO 出发做一遍bfs，用c数组存放bfs 序，他一定比他的直接下属先被 bfs 到，在上面的例子中，一个合法的bfs 序为 1 2 5 3 4，我们可以按照4 3 5 2 1 的顺序计算每个员工的团队人数。
int a[100001], size_[10001];
vector<int> sub[100001];
int main() {
int n;
cin >> n;
int c[100001];//存放bfs序
for (int i = 2; i <= n; i++) {
cin >> a[i];
sub[a[i]].push_back(i);
}
c[1] = 1;
for (int k = 1, l = 1; l <= k; l++) {
int m = c[l];
for (auto it : sub[m]) {
c[++k] = it;
}
}
for (int i = n; i; i--) {
int m = c[i];
size_[m] = 1;
for (auto it : sub[m]) {
size_[m] += size_[it];
}
}
for (int i = 1; i <= n; i++) cout << size_[i] << " ";
return 0;
}没有上司的舞会
一家公司里有 n 个员工，除了公司 CEO 外，每个人都有一个直接上司。今天公司要办一个舞会，为了大家玩得尽兴，如果某个员工的直接上司来了，他/她就不想来了。第 i 个员工来参加舞会会为大家带来 a[i] 点快乐值。请求出快乐值最大是多少。
dfs
我们只关心考虑 i 号员工的团队，他/她不参加/参加的情况下快乐值最大是几，不关心团队中具体哪些员工参加了舞会
如果i号员工参加了舞会，那么他的直接下属不参加；如果i号员工不参加舞会，那么他的直接下属可以参加也可以不参加
定义 f[i][0] 表示考虑 i 号员工的团队，他不参加的情况下的最大快乐值，定义f[i][1]表示考虑 i 号员工的团队，他参加的情况下的最大快乐值；
可得状态转移方程： f[i][0]=\sum_{j\epsilon sub[i]}^{}max(f[j][0],f[j][1])
f[i][1]=\sum_{j\epsilon sub[i]}^{}f[j][0]+a[i]
ll f[100001][2];
int a[100001];
vector<int> sub[100001];
void solve(int i) {
f[i][1] = a[i];
for (auto it : sub[i]) {
solve(it);
f[i][0] += max(f[it][1], f[it][0]);
f[i][1] += f[it][0];
}
}
int main() {
int n;
cin >> n;
for (int i = 2; i <= n; i++) {
int x; cin >> x;
sub[x].push_back(i);
}
for (int i = 1; i <= n; i++) cin >> a[i];
solve(1);
cout << max(f[1][0], f[1][1]) << endl;
return 0;
}bfs
状态转移方程与dfs相同，在计算i号员工参加或者不参加时，我们要预先知道i号员工的下属的f[j][0]和f[j][1]，因此先从 CEO 出发做一遍 bfs，用c数组存放bfs序，他一定比他的直接下属先被 bfs 到，根据得到的bfs序直接倒着转移一遍
ll f[100001][2];
int a[100001], c[100001];
vector<int> sub[100001];
int main() {
int n;
cin >> n;
for (int i = 2; i <= n; i++) {
int x; cin >> x;
sub[x].push_back(i);
}
for (int i = 1; i <= n; i++) cin >> a[i];
c[1] = 1;
for (int k = 1, l = 1; l <= k; l++) {
int m = c[l];
for (auto it : sub[m]) {
c[++k] = it;
}
}
for (int i = n; i; i--) {
int m = c[i];
f[m][1] = a[m];
for (auto it : sub[m]) {
f[m][0] += max(f[it][1], f[it][0]);
f[m][1] += f[it][0];
}
}
cout << max(f[1][0], f[1][1]) << endl;
return 0;
}新的背包
有 n 种物品要放到一个袋子里，袋子的总容量为 m ，每种物品都有 m 个，它们的体积都是 1，对于第 i 种物品，如果我们一共取了 j(j≥1) 个，会获得
w[i][j]的收益，问如何选择物品，使得在物品的总体积不超过 m 的情况下，获得最大的收益？请求出最大收益。
用f[i][j]表示考虑了前 i 种物品，总体积不超过 j 时的最大收益；
为了计算f[i][j]的值，我们枚举第 i 种物品取了 k 个，从中选择收益最大的方案，有 ：
f[i][j]=f[i-1][j-k]+w[i][k]
int f[510][510], w[510][510];
int n, m;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> w[i][j];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 0; k <= j; k++) {
f[i][j] = max(f[i][j], f[i-1][j - k] + w[i][k] );
}
}
}
cout << f[n][m];
return 0;
}可以类比01背包压缩成一维数组：
int f[510], w[510][510];
int n, m;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> w[i][j];
for (int i = 1; i <= n; i++) {
for (int j = m; j >=1; j--) {
for (int k = 0; k <= j; k++) {
f[j] = max(f[j], f[j - k] + w[i][k]);
}
}
}
cout << f[m];
return 0;
}没有上司的舞会2
一家公司里有 n 个员工，除了公司 CEO 外，每个人都有一个直接上司。今天公司要办一个舞会，为了大家玩得尽兴，如果某个员工的直接上司来了，他/她就不想来了。第 i 个员工来参加舞会会为大家带来 a[i] 点快乐值。由于场地有大小限制，场地最多只能容纳 m 个人。请求出快乐值最大是多少。
与没有上司的舞会相比多了人数限制，因此数组再加一维，
如果i号员工参加了舞会，那么他的直接下属不参加；如果i号员工不参加舞会，那么他的直接下属可以参加也可以不参加
用 f[i][k][0] 表示考虑 i 号员工的团队，他的团队中一共有不超过 k 个人参加，他不参加的情况下的最大快乐值；用f[i][k][1]表示考虑 i 号员工的团队，他的团队中一共有不超过 k 个人参加，他参加的情况下的最大快乐值；
现在我们相应的也要考虑 k —— 团队中参加舞会的人数
当 i 固定的时候，对于所有的 k，我们先来考虑如何计算 f[i][k][1]，也就是 i 号员工参加舞会的情况。考虑 i 号员工的某个直接下属 j 号员工，由于 i 号员工参加了，所以 j 号员工不会参加。j 号员工的团队中有不超过 1 人参加时的最大快乐值是 f[j][1][0]，有不超过 2 人参加时的最大快乐值是 f[j][2][0]，....，有不超过 l 人参加时的最大快乐值是 f[j][l][0]。这是不是和“新的背包”问题很像？
我们把 i 的每个直接下属 j 抽象成“新的背包”问题中的一种物品，把 j 号员工的团队中有不超过 l 人参加抽象成取了 l 个这种物品，可以获得的收益是 f[j][l][0]。就可以用“新的背包”问题的思路解决这个问题啦！现在的人数限制就是“新的背包”问题中的容量限制。
然后，对于所有的 k，我们再来考虑如何计算f[i][k][0]，也就是 i 号员工不参加舞会的情况。这种情况和 i 号员工参加舞会的情况是类似的。考虑 i 号员工的某个直接下属 j 号员工，他既可以参加也可以不参加。我们也可以把 i 的每个直接下属 j 抽象成“新的背包”问题中的一种物品，把 j 号员工的团队中有不超过 l 人参加抽象成取了 l 个这种物品，可以获得的收益是 max(f[j][l][0], f[j][l][1])，也就是在 j 号员工参加/不参加两种情况中选择快乐值较大的一个就可以啦！
ll f[510][510][2];
int a[510];
vector<int> sub[510];
int n, m;
void solve(int i) {
for (auto it : sub[i]) {
solve(it);
for (int j = m; j >= 0; j--) {
for (int k = 0; k <= j; k++) {
f[i][j][0] = max(f[i][j][0], f[i][j - k][0] + max(f[it][k][0], f[it][k][1]));
f[i][j][1] = max(f[i][j][1], f[i][j - k][1] + f[it][k][0]);
}
}
}
for (int j = m; j; j--) f[i][j][1] = f[i][j - 1][1] + a[i];
f[i][0][1] = 0;
}
int main() {
cin >> n >> m;
for (int i = 2; i <= n; i++) {
int x; cin >> x;
sub[x].push_back(i);
}
for (int i = 1; i <= n; i++) cin >> a[i];
solve(1);
cout << max(f[1][m][0], f[1][m][1]) << endl;
return 0;
}开会
一家公司里有 n 个员工，除了公司 CEO 外，每个人都有一个直接上司。公司现在要召开全员大会。为了充分传递会议信息，每个员工和他/她的直接上司至少得有一个人参加会议。由于场地限制等原因，现在我们想使得参会人数最少。请问最少需要几个人参会？
当上司参加时，员工可以选择参加或者不参加；当上司不参加时，下属必须参加；
等同于 下属参加，上司选择参加或者不参加；下属不参加，上司必须参加
可得状态转移方程：
f[i][0]=\sum_{j\epsilon sub[i]}^{}f[j][1]
f[i][1]=\{\sum_{j\epsilon sub[i]}^{}min(f[j][0],f[j][1])\}+1
每次遍历到叶子结点j时，令f[j][1] = 1, f[j][0] = 0
ll f[100010][2];
int a[100010];
vector<int>sub[100010];
void solve(int i) {
for (auto it : sub[i]) {
solve(it);
f[i][1] += min(f[it][0], f[it][1]);
f[i][0] +=f[it][1];
}
if (sub[i].empty()) f[i][1] = 1, f[i][0] = 0;
f[i][1] = f[i][1] + 1;
}
int main() {
int n;
cin >> n;
for (int i = 2; i <= n; i++) {
int x; cin >> x;
sub[x].push_back(i);
}
solve(1);
cout << min(f[1][1], f[1][0]);
return 0;
}
Last updated