廊坊集团网站建设,网站点击率多少正常,上传wordpress,郑州网络公司推荐题目描述
某大学有 n 个职员#xff0c;编号为1…n。
他们之间有从属关系#xff0c;也就是说他们的关系就像一棵以校长为根的树#xff0c;父结点就是子结点的直接上司。
现在有个周年庆宴会#xff0c;宴会每邀请来一个职员都会增加一定的快乐指数 ri#xff0c;但…
题目描述
某大学有 n 个职员编号为1…n。
他们之间有从属关系也就是说他们的关系就像一棵以校长为根的树父结点就是子结点的直接上司。
现在有个周年庆宴会宴会每邀请来一个职员都会增加一定的快乐指数 ri但是呢如果某个职员的直接上司来参加舞会了那么这个职员就无论如何也不肯来参加舞会了。
所以请你编程计算邀请哪些职员可以使快乐指数最大求最大的快乐指数。
输入格式
输入的第一行是一个整数 n。
第 2 到第 (n1) 行每行一个整数第 (i1) 行的整数表示 i 号职员的快乐指数 ri。
第 (n2) 到第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≤n≤6×10^3,−128≤ri≤1271≤l,k≤n且给出的关系一定是一棵树。
#includeiostream
#includevector
using namespace std;
const int N6e35;
int score[N];//快乐指数
bool fa[N];//判断是否有父节点
int dp[N][2];//dp[i][0]:没有结点i的最大快乐指数dp[i][1]:结点i的最大快乐指数
int n;
vectorint son[N];//son[u][i]:结点u的子结点 void dfs(int u){dp[u][1]score[u];dp[u][0]0;for(int i0;ison[u].size();i){int yson[u][i];dfs(y);dp[u][1]dp[y][0];dp[u][0]max(dp[y][0],dp[y][1]);}
}
int main(){cinn;for(int i1;in;i){cinscore[i];}for(int i0;in-1;i){int l,k;//k是l的直接上司 cinlk;son[k].push_back(l); fa[l]true; }int root1;while(fa[root]1){root; }dfs(root);coutmax(dp[root][0],dp[root][1])endl;return 0;
} 思路dp。 考虑一颗以u为根结点的子树可以分为两种情况选u和不选u。
状态表示
dp[u][0]表示以u为根节点的子树并且不包括u的最大快乐指数
dp[u][1]表示以u为根节点的子树并且包括u的最大快乐指数。
状态计算
记结点u的子结点是s1,s2
1、选udp[u][1]dp[s1][0]dp[s2][0]
2、不选udp[u][0]max(dp[s1][0]dp[s1][1])max(dp[s2][0]dp[s2][1])
