打家劫舍(三)

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int dp[100002]; // dp[i]为以i为根节点最大可偷的钱数

int dfs(int root, vector<vector<int>> &parents, vector<int> &price){
    if(root==0||parents[root].empty()){
        dp[root] = price[root]; //price[0]=0, 为空节点的价值
        return dp[root];
    }
    if(dp[root]!=-1) return dp[root];
    int l=0, r=0, ll=0, lr=0, rr=0, rl=0; //子树的根，初始为空节点
    l = parents[root][0];
    if(parents[l].size()==1){ //左子树是否有左子树
        ll = parents[l][0];
    }else if(parents[l].size()==2){ //左子树是否有左右子树
        ll = parents[l][0];
        lr = parents[l][1];
    }
    if(parents[root].size()==2){ //判断是否有右子树
        r = parents[root][1];
        if(parents[r].size()==1){ //右子树是否有左子树
            rl = parents[r][0];
        }else if(parents[r].size()==2){ //右子树是否有左右子树
            rl = parents[r][0];
            rr = parents[r][1];
        }
    }
    int res = price[root] + dfs(ll,parents,price) + dfs(lr,parents,price) + dfs(rl,parents,price) + dfs(rr,parents,price);
    res = max(res, dfs(l, parents, price)+dfs(r, parents, price));
    dp[root] = res;
    return dp[root];
}

int main() {
    int n; cin>>n;
    vector<int> price(n+1,0);
    vector<vector<int>> parents(n+1);
    for(int i=1; i<=n; i++) cin>>price[i];
    for(int i=1; i<=n; i++){
        int parent; cin>>parent;
        parents[parent].push_back(i);
    }
    memset(dp, -1, sizeof(dp));
    cout<<dfs(1, parents, price);
}

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] values = new int[n+1];
        for(int i =1;i<=n;i++){
            values[i] = in.nextInt();
        }
        //构建树
        int[] tree = new int[n+1];
        for(int i =1;i<=n;i++){
            tree[i] = in.nextInt();
        }

        //f代表偷，g代表不偷当前层
        int[] f = new int[n+1];
        int[] g = new int[n+1];

        //因为f表示该节点必偷，所以可以初始化为该节点的价值
        for(int i = 1;i<=n;i++){
            f[i]=values[i];
        }
        
        //自底向上
        for(int i =n;i>1;i--){
            f[tree[i]] += g[i]; //因为f初始化为该节点的价值，所以不用再加values[tree[i]] 这样也避免了重复的加入
            g[tree[i]] += Math.max(f[i],g[i]);
        }

        int res = Math.max(f[1],g[1]);
        System.out.println(res);

        
    }
}

#include<iostream>
#include<set>
using namespace std;

set<int> childs[100001];
int val[100001];

int dphave(int n);
int dpnone(int n);

int main(){
  int n;
  cin>>n;
  for(int i=1;i<=n;i++) cin>>val[i];
  for(int i=1;i<=n;i++) {
    int parent;
    cin>>parent;
    childs[parent].insert(i);
  }
  cout<<max(dphave(1),dpnone(1))<<endl;
}

int dpnone(int node){
  static int cache[100009];
  if(cache[node]) return cache[node];
  int result=0;
  for(int child:childs[node]){
    result+=max(dphave(child),dpnone(child));
  }
  return cache[node]=result;
}

int dphave(int node){
  static int cache[100009];
  if(cache[node]) return cache[node];
  int result=val[node];
  for(int child:childs[node]){
    result+=dpnone(child);
  }
  return cache[node]=result;
}