题解 | 打家劫舍(三)

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
vector<int> children[N];
int values[N];
int dp[N][2];  // dp[i][0]不选i, dp[i][1]选i

void dfs(int u) {
    if(children[u].empty()) {  // 叶子节点
        dp[u][0] = 0;
        dp[u][1] = values[u-1];
        return;
    }
    
    dp[u][1] = values[u-1];  // 选择当前节点
    
    for(int v : children[u]) {
        dfs(v);
        dp[u][0] += max(dp[v][0], dp[v][1]);  // 不选u时，子节点可选可不选
        dp[u][1] += dp[v][0];  // 选u时，子节点不能选
    }
}

int main() {
    int n;
    cin >> n;
    
    // 读入节点值
    for(int i = 0; i < n; i++) {
        cin >> values[i];
    }
    
    // 读入父节点关系并构建子节点表
    for(int i = 0; i < n; i++) {
        int p;
        cin >> p;
        if(p > 0) {  // 非根节点
            children[p].push_back(i+1);
        }
    }
    
    memset(dp, 0, sizeof(dp));
    dfs(1);  // 从根节点开始DFS
    
    cout << max(dp[1][0], dp[1][1]) << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static int N = 100010;
    static ArrayList<Integer>[] children;
    static int[] values;
    static int[][] dp;  // dp[i][0]不选i, dp[i][1]选i
    
    static void dfs(int u) {
        if(children[u].isEmpty()) {  // 叶子节点
            dp[u][0] = 0;
            dp[u][1] = values[u-1];
            return;
        }
        
        dp[u][1] = values[u-1];  // 选择当前节点
        
        for(int v : children[u]) {
            dfs(v);
            dp[u][0] += Math.max(dp[v][0], dp[v][1]);  // 不选u时，子节点可选可不选
            dp[u][1] += dp[v][0];  // 选u时，子节点不能选
        }
    }
    
    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        // 初始化
        values = new int[n];
        children = new ArrayList[N];
        dp = new int[N][2];
        for(int i = 0; i < N; i++) {
            children[i] = new ArrayList<>();
        }
        
        // 读入节点值
        for(int i = 0; i < n; i++) {
            values[i] = sc.nextInt();
        }
        
        // 读入父节点关系并构建子节点表
        for(int i = 0; i < n; i++) {
            int p = sc.nextInt();
            if(p > 0) {  // 非根节点
                children[p].add(i+1);
            }
        }
        
        dfs(1);  // 从根节点开始DFS
        
        System.out.println(Math.max(dp[1][0], dp[1][1]));
        
        sc.close();
    }
}

import sys
sys.setrecursionlimit(100010)

def dfs(u, values, children, dp):
    if not children[u]:  # 叶子节点
        dp[u][0] = 0
        dp[u][1] = values[u-1]
        return
    
    dp[u][1] = values[u-1]  # 选择当前节点
    
    for v in children[u]:
        dfs(v, values, children, dp)
        dp[u][0] += max(dp[v][0], dp[v][1])  # 不选u时，子节点可选可不选
        dp[u][1] += dp[v][0]  # 选u时，子节点不能选

def main():
    # 输入
    n = int(input())
    values = list(map(int, input().split()))
    parents = list(map(int, input().split()))
    
    # 构建子节点表
    children = [[] for _ in range(n+1)]
    root = 1
    for i in range(n):
        if parents[i] > 0:  # 非根节点
            children[parents[i]].append(i+1)
    
    # dp[i][0]表示不选i节点的最大值，dp[i][1]表示选i节点的最大值
    dp = [[0] * 2 for _ in range(n+1)]
    
    dfs(root, values, children, dp)
    print(max(dp[root][0], dp[root][1]))

if __name__ == "__main__":
    main()