codevs 1380 没有上司的舞会

变式题目:给定一棵树每个点有一个点权,求一个独立集使得点权和最大,树上的独立集指的是选取树上的点,使尽量多的点不直接相连

 时间限制: 1 s
 空间限制: 128000 KB
 题目等级 : 钻石 Diamond 
题目描述 Description

Ural大学有N个职员,编号为1~N。他们有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会,要求与会职员的快乐指数最大。但是,没有职员愿和直接上司一起与会。

输入描述 Input Description

第一行一个整数N。(1<=N<=6000)
接下来N行,第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)
接下来N-1行,每行输入一对整数L,K。表示K是L的直接上司。
最后一行输入0,0。

输出描述 Output Description

输出最大的快乐指数。

样例输入 Sample Input

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

样例输出 Sample Output

5

数据范围及提示 Data Size & Hint

各个测试点1s

分类标签 Tags

动态规划 树型DP

 /*树形Dp:一般以节点作为状态划分的点。
对于当前的节点代表的人:
1.这个人去舞会,那么他的下属一定不去,状态转移到子节点
2.这个人不去舞会,但是他的下属也不一定会去,因为不一定是最优,就是在子节点去与不去间取最优
树形Dp一般从根节点开始记忆化搜索来实现。
*/
#include<iostream>
using namespace std;
#include<cstdio>
#define N 8000
struct Edge{
int v,last;
}edge[N];
bool flag[N];/*找根节点*/
int f[N][],val[N];/*f[i][1]代表当前节点去舞会的这棵子树上快乐最大值,f[i][0]代表当前节点不去舞会的这棵子树上快乐最大值,*/
int head[N]={},cnt=;
int n;
void add_edge(int u,int v)
{
++cnt;
edge[cnt].v=v;/*建立边表*/
edge[cnt].last=head[u];
head[u]=cnt;
}
void dp(int u)
{
f[u][]=;/*搜索的边界就是没有下属的人,就是f[u][1]=val[u]; f[u][0]=0;*/
f[u][]=val[u];
for(int l=head[u];l;l=edge[l].last)/*对于有下属的人,必须知道他的下属情况才能判断*/
{
int v=edge[l].v;
dp(v);/*搜索下属*/
f[u][]=max(f[u][],f[u][]+f[v][]);/*注意这是在for循环中当前点的f[v][0]会被加了多次,v不同*/
f[u][]=f[u][]+max(f[v][],f[v][]);/*当前节点不去,就判断他的某个子节点去还是不去最优*/
}
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;++i)
scanf("%d",&val[i]);
for(int i=;i<n;++i)
{
int u,v;
scanf("%d%d",&v,&u);
flag[v]=true;/*给有父节点的点标上标记*/
add_edge(u,v);
}
int u,v;
scanf("%d%d",&u,&v);
for(int i=;i<=n;++i)
if(!flag[i])/*找到根节点*/
{
dp(i);
printf("%d\n",max(f[i][],f[i][]));
break;
}
return ;
}

最新文章

  1. React学习笔记-7-销毁阶段
  2. Expression Blend 4 学习笔记
  3. lvs+keeplived笔录
  4. iOS阶段学习第一天笔记(Mac终端的操作)
  5. SharePoint 2013 - REST API about Content
  6. 分分钟学会使用memcached
  7. jQuery+css3弹出框插件
  8. WPF九宫格HLSL版
  9. pt-tcp-model
  10. location对象浅探
  11. sql必知必会笔记
  12. MySQL数据库快速造大量数据
  13. 38.Odoo产品分析 (四) – 工具板块(7) – 车队管理(2)
  14. (转)SQLServer_十步优化SQL Server中的数据访问 二
  15. 计算机网络三:域名、IP地址和TCP/IP协议
  16. linux执行python命令后没有反应,不打印日志信息
  17. zabbix之 自定义(指定特定磁盘)监控io
  18. Character Encoding Issues for tomcat
  19. Java集合-----Map详解
  20. spring整合quartz时间任务调度框架

热门文章

  1. [译]Asp.net MVC 之 Contorllers(一)
  2. iOS-详细解读Const
  3. ios awakeFromNib 和 initWithCoder:
  4. Educational Codeforces Round 14 D. Swaps in Permutation
  5. nodejs+express使用html和jade
  6. ASP.NET MVC请求处理管道生命周期的19个关键环节(13-19)
  7. [DevExpress]SplitContainerControl使用小计
  8. js 之 Post发送请求
  9. 如果一个Object对象可能是数组那么如何对其进行迭代
  10. Webserver管理系列:3、Windows Update
  11. Docker最全教程——从理论到实战(一)
  12. AbstractMethodError:
  13. Python全栈之路----常用模块----hashlib加密模块
  14. php7.2 sqlsrv 扩展 ubuntu Homestead centOs
  15. git checkout tags with the same name as a branch
  16. Spark安装与介绍
  17. 「PKUSC2018」真实排名(排列组合,数学)
  18. laravel 处理自定错误页面,如404,500,501,502,503,504等等
  19. delphi 线程的应用 和spcomm的应用
  20. Fidder发送Get、POST请求