树形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;
}