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][0/1] 表示以 i 为节点的子树所能得到的最大的气氛值。
• f[i][0] 表示以 i 为子树且未选择 i 号节点；
• f[i][1] 表示以 i 为子树且选择了 i 号节点
• 最终答案就是 max(f[root][0], f[root][1])

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
int n,a[6006], x, t,cnt,tot,head[6006], dp[6006][2];
struct edge
{int to,next;
}e[6006];
void add(int x,int y)
{e[++tot].to= y;e[tot].next = head[x];head[x] = tot;
}
int solve(int i,int d)
{if(dp[i][d])return dp[i][d];if(d==1){dp[i][d] += a[i];for (int ii = head[i]; ii!= -1;ii=e[ii].next){int tt = e[ii].to;dp[i][d] += solve(tt, 0);}return dp[i][d];}else{for (int ii = head[i]; ii != -1; ii = e[ii].next){int tt = e[ii].to;dp[i][d] += max(solve(tt, 0), solve(tt, 1));}return dp[i][d];}}
int main()
{while (scanf("%d", &n) && n){int ans = 0;memset(dp, 0, sizeof(dp));memset(head, -1, sizeof(head));for (int i = 1; i <=n; i++){scanf("%d", &a[i]);} for (int i = 0; i <n-1; i++){scanf("%d%d", &x, &t);add( t,x);}for (int i = 1; i <= n;i++)//开始{ans=max(ans,max(solve(i, 0),solve(i, 1)));}printf("%d\n",ans);}
//    system("pause");return 0;
}