[数据结构与算法]没有上司的舞会---树形dp

没有上司的舞会

考点： 树形$dp$

思路：$dp[u][0]$表示第u个结点不去产生的最大价值，$dp[u][1]$表示第u个结点去产生的最大价值，状态转移方程为，设j为u的儿子结点：

$$?\begin{array}{l}dp[u][0]=dp[u][0]+\sum max(dp[j][1],dp[j][0])\\ \\ dp[u][1]=dp[u][1]+\sum dp[j][0]+w[u]\end{array}$$

从根结点$dfs$一遍即可。

#include <bits/stdc++.h>

using namespace std;

typedef long long  LL;
const int N = 100010;

int n;
int h[N], ne[N], e[N], idx;
int w[N];
LL dp[N][2];

void add(int a, int b){
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

LL dfs(int u){
	dp[u][1] = w[u];
	for(int i = h[u]; ~i; i = ne[i]){
		int j = e[i];
		dfs(j);
		dp[u][0] = dp[u][0] + max(dp[j][1], dp[j][0]);
		dp[u][1] = dp[u][1] + dp[j][0];
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin >> n;
	memset(h, -1, sizeof h);
	for(int i = 2; i <= n; i ++ ){
		int x;
		cin >> x;
		add(x, i);
	}
	for(int i = 1; i <= n; i ++ ){
		cin >> w[i];
	}
	dfs(1);
	LL ans = -1;
	for(int i = 1; i <= n; i ++ ){
		ans = max({ans, dp[i][1], dp[i][0]});
	}
	cout << ans;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖