Week13 作业 D - TT 的苹果树（选做）

一、题目描述

在大家的三连助攻下，TT 一举获得了超级多的猫咪，因此决定开一间猫咖，将快乐与大家一同分享。并且在开业的那一天，为了纪念这个日子，TT 在猫咖门口种了一棵苹果树。
一年后，苹果熟了，到了该摘苹果的日子了。
已知树上共有 N 个节点，每个节点对应一个快乐值为 w[i] 的苹果，为了可持续发展，TT 要求摘了某个苹果后，不能摘它父节点处的苹果。
TT 想要令快乐值总和尽可能地大，你们能帮帮他吗？

Input

结点按 1～N 编号。
第一行为 N (1 ≤ N ≤ 6000) ，代表结点个数。
接下来 N 行分别代表每个结点上苹果的快乐值 w[i]（-128 ≤ w[i] ≤ 127)。
接下来 N-1 行，每行两个数 L K，代表 K 是 L 的一个父节点。
输入有多组，以 0 0 结束。

Output

每组数据输出一个整数，代表所选苹果快乐值总和的最大值。

输入样例

7
1
1
1
1
1
1
1
1 3
7 4
2 3
4 5
6 4
3 5
0 0

输出样例

5

二、思路概述

• 用f[i]表示以i为根节点的子树的权值的最大值，f[i][0]表示不选i节点,f[i][1]表示选i节点。
• 转移方程为f[x][0]+=max(f[*it][0],f[*it][1]); f[x][1]+=f[*it][0]+w[x];

三、完整代码

#include 
#include 
#include
using namespace std;
const int maxn=6000+10;
int w[maxn];
int f[maxn][2];
bool vis[maxn];
int n;
vector<int> e[maxn];//用来保存父子关系，s[i]里面存储着i的孩子 void dfs(int x)
{vis[x]=true;//表示x已经被dfs过了 for(vector<int>::iterator it=e[x].begin();it!=e[x].end();it++){if(!vis[*it])dfs(*it);f[x][0]+=max(f[*it][0],f[*it][1]);//当不选父节点时，f[x][0]加上它子节点的f中的较大值 }for(vector<int>::iterator it=e[x].begin();it!=e[x].end();it++){if(!vis[*it])dfs(*it);f[x][1]+=f[*it][0];//当选父节点时，f[x][1]加上它子节点不选的f }f[x][1]+=w[x];//加上自己的权值 }void solve(){int ans=0;memset(f,0,sizeof(f));for(int i=1;i<=n;i++){if(!vis[i])dfs(i);int temp=max(f[i][0],f[i][1]);ans=max(ans,temp);}printf("%d\n",ans);}
int main(){while(scanf("%d",&n)!=EOF){if(n==0)break;for(int i=1;i<=n;i++)scanf("%d",&w[i]);//每个结点上苹果的快乐值 w[i]（-128 ≤ w[i] ≤ 127)for(int i=0;i<n-1;i++){//每行两个数 L K，代表 K 是 L 的一个父节点。int l,k;scanf("%d%d",&l,&k);e[k].push_back(l);}solve(); }
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！