树形DP-AcWing 285. 没有上司的舞会-XMUOJ提瓦特庆典策划

本文主要是介绍树形DP-AcWing 285. 没有上司的舞会-XMUOJ提瓦特庆典策划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

 

思路

话不多说，直接上代码 

代码 

/*
AcWing 285. 没有上司的舞会-XMUOJ提瓦特庆典策划
--JinlongW-2024/05/26 
*/
#include <bits/stdc++.h>
using namespace std;
const int N=7000;
int st[N];//标记是否有父亲结点
int happy[N];
int dp[N][2];
vector<int>son[N];
int n;void DP(int x){//初始化 dp[x][0]=0;dp[x][1]=happy[x];//沿着子树进行深度搜索 for(int i=0;i<son[x].size();i++){ //对子树进行深度搜索 int y=son[x][i];DP(y);dp[x][0]+=max(dp[y][0],dp[y][1]);dp[x][1]+=dp[y][0]; }
} 
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>happy[i];}for(int i=1;i<n;i++){int x,y;cin>>x>>y;st[x]=1;son[y].push_back(x); } int root=0;for(int i=1;i<=n;i++){if(st[i]==0){root=i;break;}}DP(root);cout<<max(dp[root][0],dp[root][1])<<endl; return 0;
}

这篇关于树形DP-AcWing 285. 没有上司的舞会-XMUOJ提瓦特庆典策划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---