题解 | #打家劫舍(三)#

树状dp，一般需要遍历树。方式是深度遍历。
这个题，节点用输入数值的下标来表示，如图所示：
f[i][0]表示 以i为根的子树，并且不包括节点i（最大值不包括节点的值）的最大值，该状态可以来自于左右子树（如果存在）的max(f[左子树][0], f[左子树][1])+max(f[右子树][0], f[右子树][1])
f[i][1]表示 以i为根的子树，并且包括节点i（最大值包括节点的值）的最大值，该状态可以来自于f[左子树][0]+f[右子树][0]+a[i]

#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int n;
//用邻接表存储二叉树
int h[N], e[N], ne[N], idx;

void add(int a, int b) // a是父节点 b是子节点
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int f[N][2];
int a[N];
void dfs(int u){
    f[u][1] = a[u];
    for(int i = h[u]; i!= -1; i = ne[i]){
        int j = e[i];
        dfs(j);
        f[u][1] += f[j][0]; // 父节点选了，子节点不能选了
        f[u][0] += max(f[j][0], f[j][1]);
    }
}
int main() {
    cin >> n;
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    int root = -1;
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        if(x==0) root = i;
        add(x, i);  // a_x 是a_i的父节点
    }
    dfs(root);
    cout << max(f[root][0], f[root][1]);
    return 0;
}