题目

题目描述

某大学有 $n$ 个职员，编号为 $1\dots n$。

他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数$r_i$ ，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

输入格式

输入的第一行是一个整数 $n$。

第 $2$ 到第 $(n+1)$ 行，每行一个整数，第 $(i+1)$行的整数表示 $i$ 号职员的快乐指数$ r_i$ 。

第$ (n + 2)$到第 $2n$ 行，每行输入一对整数 $l,k$，代表 $k$ 是 $l$ 的直接上司。

输出格式

输出一行一个整数代表最大的快乐指数。

输入输出样例

输入

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

输出

5

说明/提示

数据规模与约定 对于 $100\%$ 的数据，保证$1\le n\le 6\times 10^3$，$-128\le r_i\le 127$,$1\le l,k\le n$，且给出的关系一定是一棵树。

题解

我们设$dp[i][1]$表示$i$要来的情况下以$i$为根节点的子树的最大快乐值 $dp[i][0]$表示$i$不来的情况下以$i$为根节点的子树的最大快乐值

若$i$要来，那么他的每一个子节点都只能不来，$dp[i][1]=\sum dp[j][0]，j为i的子节点$

如果ta不来，那么他的每个子节点就可来可不来，$dp[i][0]=\sum max(dp[j][0],dp[j][1]),j为i的子节点$

我们需要从每个叶子节点向上不断跟新dp，直到求到根节点，这一步我们可以用递归的方式，对于每一个节点，先递归他的每一个子节点，再在回溯时执行更新操作

最终的答案就是看根节点是去还是不去，$max(dp[root][1],dp[root][0])$’

Code:

#include<cstdio> #include<iostream> #include<vector> using namespace std; const int MAXN=6005; int h[MAXN]; vector<int> son[MAXN]; bool flag[MAXN]; int dp[MAXN][5]; int Max(int a,int b){ return a<b?b:a; } int Min(int a,int b){ return a<b?a:b; } void dfs(int x){ dp[x][0]=0; dp[x][1]=h[x]; for(int i=0;i<son[x].size();i++){ int y=son[x][i]; dfs(y); dp[x][0]+=Max(dp[y][0],dp[y][1]); dp[x][1]+=dp[y][0]; } } int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&h[i]); } for(int i=1;i<=n-1;i++){ int l,k; scanf("%d %d",&l,&k); son[k].push_back(l); flag[l]=1; } int root; for(int i=1;i<=n;i++){ if(!flag[i]){ root=i; break; } } dfs(root); printf("%d",Max(dp[root][1],dp[root][0])); return 0; }