AcWing 285. 没有上司的舞会
原题链接
简单
作者:
CqAq
,
2024-04-09 19:08:42
,
所有人可见
,
阅读 4
算法1
C++ 代码
#include<bits/stdc++.h>
using namespace std;
//一种对各自的父节点有操作,然后对于他们的儿子节点有一定的影响限制
int n;
const int N = 1e4 + 1;
int happ[N];
bool st[N];
vector<int> E[N];
int f[N][2];//N个结点,有去和不去两种情况
void dfs(int root){
f[root][1] = happ[root];//初始化,,也是来了才有happ值
for(int i = 0; i < E[root].size(); ++ i){
dfs(E[root][i]);
int p = E[root][i];
f[root][1] += f[p][0]; //累加每一个happ,,上司去我不去
f[root][0] += max(f[p][1], f[p][0]);//上司不去,我去---主打叛逆
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n;
for(int i = 1; i <= n; ++ i) cin >> happ[i];
//不知道谁是根节点,,,记录一下谁没有父亲
for(int i = 1; i < n; ++ i){
int l, k; cin >> l >> k;
st[l] = true;
E[k].push_back(l);
}
int root = 1;
while(st[root]) root ++;// 直到第一个没有父亲的false退出
dfs(root); //因为单项,所以不需要记录父亲了
cout << max(f[root][1], f[root][0]);//取根的来与不来的最大值,最
return 0;
}