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

解题思路：

• 题目规定不能连续相邻两个房间偷，令$d{p}_{i,0\mathrm{/}1}dp\_\{i,0/1\}$来表示节点$ii$为根可以偷到的最大价值，最终结果即$\max (d{p}_{1,0},d{p}_{1,1})\backslash max(dp\_\{1,0\},dp\_\{1,1\})$。
• 假设$ii$被偷，则有：$d{p}_{i,1}+=d{p}_{i^{\mathrm{\prime }}sson,0}dp\_\{i,1\}\; +=\; dp\_\{i\text{'}s\backslash \; son,0\}$
• 假设$ii$没被偷， 则有$d{p}_{i,0}+=\max (d{p}_{i^{\mathrm{\prime }}sson,0},d{p}_{i^{\mathrm{\prime }}sson,1})dp\_\{i,0\}\; +=\; \backslash max(dp\_\{i\text{'}s\backslash \; son,0\},dp\_\{i\text{'}s\backslash \; son,1\})$注意$ii$即使不偷，$ii$的孩子也可以偷或不偷，而不是一定要偷，取最大值即可。

#include<bits/stdc++.h>
using namespace std;
struct edge{
    int to, next;
}es[200005];
int head[100005], w[100005];
int cnt = 0;
void add_edge(int from, int to){//建图
    es[++cnt].to = to;
    es[cnt].next = head[from];
    head[from] = cnt;
}
int dp[100005][2];
void solve(int i){
    for(int j = head[i]; j; j = es[j].next){
        solve(es[j].to);//先处理son
        dp[i][1] += dp[es[j].to][0];//在偷的情况下，应该是其son不偷的情况下的最大值。
        dp[i][0] += max(dp[es[j].to][0],dp[es[j].to][1]);//在不偷的情况下，应该取son偷或不偷所产生的最大值。
    }
    return;
}
int main(){
    int n;
    int root;
    cin>>n;
    for(int i = 1; i <= n; ++i) cin>>dp[i][1];//初始化dp
    for(int i = 1; i <= n; ++i){
        int fa;
        cin>>fa;
        if(fa == 0) root = i;
        else{
            add_edge(fa, i);
        }
    }
    solve(root);
    cout<<max(dp[root][0], dp[root][1]);
    return 0;
}