7-2 运动会 (10 分)_t公司的员工层级关系可以表示成一棵树,员工x是员工y的直接领导,则在树中x是y的父-程序员宅基地

7-2 运动会 (10 分)

题目

T公司的员工层级关系可以表示成一棵树，员工X是员工Y的直接领导，则在树中X是Y的父结点。公司拟组织一场运动会，但为了避免尴尬，每个员工都不想与自己的直接领导一起参赛。假定每个员工都对应一个权重（领导的权重不一定比下属大），请你编写程序，邀请若干员工参赛，使得参赛人员的总权重和最大。

输入格式

第一行一个正整数n，表示公司的员工人数，员工编号为1…n，n不超过3000。接下来n行，每行1个整数，表示每个员工的权重，值域为[−27 , 27)。接下来n-1行，每行为两个空格间隔的整数X和Y，表示Y是X的直接领导。

输出格式

输出为一个整数，表示参赛员工的最大权重之和。

输入样例

输出样例

基本思路

数组wi[maxn]，下表为节点编号，值为为每个结点的权值。
利用邻接表vector v[maxn]来记录这棵多叉树。
找到根结点，用root保存。
分别使用数组记录每个结点的两种状态：

dp_join[i] 存储：当结点i加入时，该结点和它的下属结点所能得到的最大值
dp_no[i]存储：//当结点i不加入时，它的下属结点所能得到的最大值
则
状态转移方程为

递推边界为
dp_join[root] = wi[root]和dp_no[root] = 0//这里的root为叶子结点。

从根结点开始dfs，由叶子结点（递推边界）到根节点，维护dp_join[]和dp_no[]即可。
则答案即为 max(dp_join[root],dp_no[root])。

代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=3005;

int n,root=1;//员工人数。根结点编号，初始化为1
bool hash_table[maxn];//下标为结点编号，值表示该结点是否是孩子结点
int wi[maxn];//下标为结点编号，值为结点权值
vector<int> v[maxn];//下标为结点编号，值为该结点的孩子结点的编号
//每个结点有如下两种状态（简称：状态一 和 状态二），含义请看注释
int dp_join[maxn];//当结点i加入时，该结点和它的下属结点所能得到的最大值
int dp_no[maxn];//当结点i不加入时，它的下属结点所能得到的最大值
//
void solve(int root){
    
    //递推边界（叶子结点）
    if(v[root].size()==0){
    
        dp_join[root] = wi[root];
        dp_no[root] = 0;
        return;
    }
    dp_join[root] = wi[root];
    /*因为当前结点的状态由它的子节点的状态推导而来，所以需要先dfs当前结点的子结点
    把它的子节点的两种状态计算出来，再回溯回来更新当前结点的两种状态
    当它的所有子节点的两种状态全部考虑完毕，当前结点的两种状态也随之确定*/
    //当前结点的状态一dp_join[root]=wi[root]+每个子结点的状态二dp_no[wi[v[root][i]]]
    //上面这句话说明如果选了当前结点，那么它的子节点全部不能选，那只能选择子节点没有选的状态相加
    //当前结点的状态二dp_no[root]=每个子结点的状态一/状态二的最大值
    //上面这句话说明如果没选当前结点，那么它的子节点全部能选能不选，那选择子节点两种状态的较大者相加
    for (int i = 0; i < v[root].size();i++){
    
        solve(v[root][i]);
        dp_join[root] += dp_no[v[root][i]];
        dp_no[root] += max(dp_no[v[root][i]], dp_join[v[root][i]]);
    }
}
int main(){
    
    cin>>n;
    //读入每个结点的权值
    for(int i=1;i<=n;i++){
    
        cin>>wi[i];
    }
    //构建这棵树，并找出根结点编号
    for(int i=0;i<n-1;i++){
    
        int ans1,ans2;
        cin>>ans1>>ans2;
        v[ans2].push_back(ans1);
        hash_table[ans1]=true;
    }
    while(hash_table[root]) root++;
    //从根结点开始对这棵二叉树进行dfs，求出每个结点两种状态
    solve(root);
    //所能获得的最大权值就是dp_join[root]和dp_no[root]中的更大者
    cout << max(dp_join[root], dp_no[root]) << endl;
    return 0;
}

本文链接：https://blog.csdn.net/Baifeili/article/details/121002457

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

HTML5 Web SQL 数据库_方式准则的定义-程序员宅基地

文章浏览阅读1k次。1、HTML5 Web SQL 数据库 Web SQL 数据库 API 并不是 HTML5 规范的一部分，但是它是一个独立的规范，引入了一组使用 SQL 操作客户端数据库的 APIs。如果你是一个 Web 后端程序员，应该很容易理解 SQL 的操作。Web SQL 数据库可以在最新版的 Safari, Chrome 和 Opera 浏览器中工作。2、核心方法以下是规范中定义的三个_方式准则的定义

spring Boot 中使用线程池异步执行多个定时任务_springboot启动后自动开启多个线程程序-程序员宅基地

文章浏览阅读4.1k次，点赞2次，收藏6次。spring Boot 中使用线程池异步执行多个定时任务在启动类中添加注解@EnableScheduling配置自定义线程池在启动类中添加注解@EnableScheduling第一步添加注解，这样才会使定时任务启动配置自定义线程池@Configurationpublic class ScheduleConfiguration implements SchedulingConfigurer..._springboot启动后自动开启多个线程程序

Maven编译打包项目 mvn clean install报错ERROR_mvn clean install有errors-程序员宅基地

文章浏览阅读1.1k次。在项目的target文件夹下把之前"mvn clean package"生成的压缩包(我的是jar包)删掉重新执行"mvn clean package"再执行"mvn clean install"即可_mvn clean install有errors

navacate连接不上mysql_navicat连接mysql失败怎么办-程序员宅基地

文章浏览阅读974次。Navicat连接mysql数据库时，不断报1405错误，下面是针对这个的解决办法：MySQL服务器正在运行，停止它。如果是作为Windows服务运行的服务器，进入计算机管理--->服务和应用程序------>服务。如果服务器不是作为服务而运行的，可能需要使用任务管理器来强制停止它。创建1个文本文件(此处命名为mysql-init.txt)，并将下述命令置于单一行中：SET PASSW..._nvarchar链接不上数据库

Python的requests参数及方法_python requests 参数-程序员宅基地

文章浏览阅读2.2k次。Python的requests模块是一个常用的HTTP库，用于发送HTTP请求和处理响应。_python requests 参数

近5年典型的的APT攻击事件_2010谷歌网络被极光黑客攻击-程序员宅基地

文章浏览阅读2.7w次，点赞7次，收藏50次。APT攻击APT攻击是近几年来出现的一种高级攻击，具有难检测、持续时间长和攻击目标明确等特征。本文中，整理了近年来比较典型的几个APT攻击，并其攻击过程做了分析（为了加深自己对APT攻击的理解和学习）Google极光攻击2010年的Google Aurora(极光)攻击是一个十分著名的APT攻击。Google的一名雇员点击即时消息中的一条恶意链接，引发了一系列事件导致这个搜_2010谷歌网络被极光黑客攻击

随便推点

微信小程序api视频课程-定时器-setTimeout的使用_微信小程序 settimeout 向上层传值-程序员宅基地

文章浏览阅读1.1k次。JS代码 /** * 生命周期函数--监听页面加载 */ onLoad: function (options) { setTimeout( function(){ wx.showToast({ title: '黄菊华老师', }) },2000 ) },说明该代码只执行一次..._微信小程序 settimeout 向上层传值

uploadify2.1.4如何能使按钮显示中文-程序员宅基地

文章浏览阅读48次。uploadify2.1.4如何能使按钮显示中文博客分类：uploadify网上关于这段话的搜索恐怕是太多了。方法多也试过了不知怎么，反正不行。最终自己想办法给解决了。当然首先还是要有fla源码。直接去管网就可以下载。[url]http://www.uploadify.com/wp-content/uploads/uploadify-v2.1.4...

戴尔服务器安装VMware ESXI6.7.0教程（U盘安装）_vmware-vcsa-all-6.7.0-8169922.iso-程序员宅基地

文章浏览阅读9.6k次，点赞5次，收藏36次。戴尔服务器安装VMware ESXI6.7.0教程（U盘安装）一、前期准备1、下载镜像下载esxi6.7镜像：VMware-VMvisor-Installer-6.7.0-8169922.x86_64.iso这里推荐到戴尔官网下载，Baidu搜索“戴尔驱动下载”，选择进入官网，根据提示输入服务器型号搜索适用于该型号服务器的所有驱动下一步选择具体类型的驱动选择一项下载即可待下载完成后打开软碟通（UItraISO），在“文件”选项中打开刚才下载好的镜像文件然后选择启动_vmware-vcsa-all-6.7.0-8169922.iso