求二叉树的最长路径_某完全二叉树按层次输出,从左到右

求二叉树的最长路径_某完全二叉树按层次输出,从左到右Ural 大学有 N 名职员,编号为 1∼N。他们的关系就像一棵以校长为根的树,父节点就是子节点的直接上司。每个职员有一个快乐指数,用整数 Hi 给出,其中 1≤i≤N。现在要召开一场周年庆宴会,不过,没有职员愿意和直接上司一起参会。在满足这个条件的前提下,主办方希望邀请一部分职员参会,使得所有参会职员的快乐指数总和最大,求这个最大值。输入格式第一行一个整数 N。接下来 N 行,第 i 行表示 i 号职员的快乐指数 Hi。接下来 N−1 行,每行输入一对整数 L,K,表示 K 是 L 的直接

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

Ural 大学有 N 名职员,编号为 1∼N。

他们的关系就像一棵以校长为根的树,父节点就是子节点的直接上司。

每个职员有一个快乐指数,用整数 Hi 给出,其中 1≤i≤N。

现在要召开一场周年庆宴会,不过,没有职员愿意和直接上司一起参会。

在满足这个条件的前提下,主办方希望邀请一部分职员参会,使得所有参会职员的快乐指数总和最大,求这个最大值。

输入格式
第一行一个整数 N。

接下来 N 行,第 i 行表示 i 号职员的快乐指数 Hi。

接下来 N−1 行,每行输入一对整数 L,K,表示 K 是 L 的直接上司。

输出格式
输出最大的快乐指数。

数据范围
1≤N≤6000,
−128≤Hi≤127

输入样例:
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
输出样例:
5

题解
f[i][0]:节点0没有选,树的最大值
f[i][1]:节点0选了,树的最大值

#include<bits/stdc++.h>
using namespace std;
const int N = 6e3 + 10;
int f[N][2],a[N],in[N];
struct Edge{ 
   
    int v,next;
}edge[N];
int head[N],cnt;
void add(int u,int v){ 
   
    edge[cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
int dfs(int u){ 
   
    for(int i = head[u];~i;i = edge[i].next){ 
   
        int v = edge[i].v;
        dfs(v);
        f[u][0] += max(f[v][1],f[v][0]);
        f[u][1] += f[v][0];
    }
    f[u][1] += a[u];
}
int main(){ 
   
    int n,root = -1;
    cin>>n;
    memset(head,-1,sizeof head);
    int x,y;
    for(int i = 1;i <= n;i ++)cin>>a[i];
    for(int i = 0;i < n - 1;i ++){ 
   
        cin>>x>>y;
        add(y,x);
        in[x] ++;
    }
    for(int i = 1;i <= n;i ++)
        if(in[i] == 0)root = i;
    dfs(root);
    cout<<max(f[root][0],f[root][1]);
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168674.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 如何关闭或启动mysql服务器_MySQL运行

    如何关闭或启动mysql服务器_MySQL运行方法一:通过命令行开启\关闭服务第一步点击开始菜单,找到cmd,以管理员身份运行。第二步在命令行里面输入“netstopmysql”,按回车键,就停止了mysql服务,如下图所示:第三步在命令行输入“netstartmysql”,接着按回车键,开启mysql服务,如下图所示:END方法二:通过电脑服务开启/关闭第一步最开始右键计算机,选择“管理”,如下图所示:第二步进去管理之后,选择服务和…

    2022年10月25日
  • 希尔伯特黄变换信号处理_希尔伯特变换后频谱图

    希尔伯特黄变换信号处理_希尔伯特变换后频谱图希尔伯特黄变换(Hilbert-Huang)包括两部分工作,分别是经验模态分解(EMD)和希尔伯特变换(HT)。经验模态分解:找到信号x(t)的极大值和极小值,通过三次样条拟合得到上、下包络线,计算其均值得m1(t). 得到第一个分量,检擦其是否满足模态分量的条件:①得极大值点与过0点数量相差不超过1个;②的上、下包络线均值恒为0。如不满足,重复操作1、2直至得到满足模态函数…

    2022年10月14日
  • mysql字符串截取函数_excel 截取部分字符

    mysql字符串截取函数_excel 截取部分字符MySQL 字符串截取函数:left(), right(), substring(), substring_index()。还有 mid(), substr()。其中,mid(), substr() 等价于 substring() 函数,substring() 的功能非常强大和灵活。  1. 字符串截取:left(str, length)  mysql> select left(‘sqls

  • 智慧小区智能物业管理系统综合解决方案_智能小区管理系统

    智慧小区智能物业管理系统综合解决方案_智能小区管理系统因为传统的办公方式效率低,工作强度大。人们需耗费大量的时间和精力去手工处理那些繁杂、重复的工作,而手工处理的延时和差错,正是现代化管理中应该去除的弊端。又由于物业管理企业的启动基金不足,多种经营服务不善等,导致招不到专业水平高的工作人员,再加上管理手段落后,所以就很难提高物业管理企业的效益。小区管理在手工操作时代,工作非常繁琐,需要大量的人力、物力和财力,极大的浪费了小区物业的资源。而这些项目在过去手工操作时代,需要手工记录这些事情,不但麻烦琐碎,还经常出现错误,给广大业主带来很不便,正是适应这种社…

    2022年10月18日
  • python 0o_python中0o1010是多少

    python 0o_python中0o1010是多少python0o1010是多少?它以0开头,满足八进制的要求,是个八进制的数,下面来了解一下整数的四种表现形式:对于整数:有四种表现形式二进制:0,1满2进1八进制:0-7满8进1,用0开头表示十进制:0-9满10进1十六进制:0-9,A-F满16进1,用0x表示位(bit):存储信息的最小单位,表示一个二进制数字。字节(Byte):一个字节由8位二进制数字组成(1Byte=8bit)…

  • ubuntu 7.04 ‘s sources list

    ubuntu 7.04 ‘s sources list

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号