当前位置: 首页 > news >正文

蓝桥杯 9.生命之树

生命之树

原题目链接

题目描述

在 X 森林里,上帝创建了生命之树。

他给每棵树的每个节点(叶子也称为一个节点)上,都标了一个整数,代表这个点的和谐值。

上帝要在这棵树内选出一个节点集 S,使得对于 S 中任意两个点 a, b,都存在一个点列:

a, v1, v2, …, vk, b

使得这个点列中的每个点都是 S 里面的元素,且序列中相邻两个点之间有一条边相连。

在这个前提下,上帝希望 S 中所有节点的整数和尽量大。

这个最大的和就是上帝给生命之树的评分。

注意:集合 S 可以为空。


输入描述

  • 第一行一个整数 n,表示这棵树有 n 个节点。
  • 第二行 n 个整数,依次表示每个节点的评分。
  • 接下来 n-1 行,每行两个整数 u, v,表示存在一条 u 到 v 的边。

保证:

  • 1 <= n <= 100000
  • 每个节点的评分的绝对值不超过 1000000

输出描述

输出一行一个整数,表示上帝给这棵树的最大评分。


输入输出样例

输入

5
1 -2 -3 4 5
4 2
3 1
1 2
2 5

输出

8

c++代码

#include<bits/stdc++.h>
#include<stdio.h>using namespace std;typedef long long ll;ll n, a, b, ans = 0;
vector<ll> trees, dp, know;
vector<vector<ll>> edges;void dfs(ll root) {know[root] = 0;dp[root] += trees[root];for (ll x : edges[root]) {if (!know[x]) continue;dfs(x);if (dp[x] > 0) dp[root] += dp[x];}ans = max(ans, dp[root]);
}int main() {scanf("%lld", &n);edges = vector<vector<ll>>(n + 1);trees = vector<ll>(n + 1, 0), dp = vector<ll>(n + 1, 0), know = vector<ll>(n + 1, 1);for (ll i = 1; i <= n; i++) scanf("%lld", &trees[i]);for (ll i = 0; i < n - 1; i++) {scanf("%lld %lld", &a, &b);edges[a].push_back(b);edges[b].push_back(a);}dfs(1);cout << ans;return 0;
}//by wqs

思路解析

题目的意思就是要我们找一颗子树,使得这颗子树的权值和最大。

http://www.xdnf.cn/news/180991.html

相关文章:

  • 【Multipath】dm软链接相关问题定位
  • 前端高频面试题day3
  • Python装饰器:函数增强的秘密武器
  • 使用ZXing开发安卓扫码功能
  • 【C++】C++11新特性(一)
  • 【前端】element表格X轴滚动优化拖拽滚动
  • 函数式编程之 Optional
  • 海底世界-第16届蓝桥第4次STEMA测评Scratch真题第5题
  • 【jax】ms(毫秒)和 μs(微秒)
  • Leetcode395.至少有 K 个重复字符的最长子串
  • Qt从零开始(1)了解
  • Golang | 倒排索引Value的设计
  • Python爬虫实战:获取ya马逊最新销售飙升榜数据并做分析,为电商选品做参考
  • 【AI】MCP协议,AI界的USB接口
  • FastAPI系列06:FastAPI响应(Response)
  • leetcode--盛最多水的容器,接雨水
  • 数值分析、数值代数之追赶法
  • Linux课程五课---Linux进程认识1
  • MySQL----查询
  • 树莓派超全系列教程文档--(43)树莓派内核简介及更新
  • 机器学习基础——Seaborn使用
  • C++11
  • 自然语言处理之机器翻译:Statistical Machine Translation(SMT)的评估方法解析与创新实践
  • 小集合 VS 大集合:MySQL 去重计数性能优化
  • 常用第三方库:sqflite数据库应用
  • Python语言基础知识详解:数据类型及运算
  • 【MQ篇】RabbitMQ之消费失败重试!
  • 2、Linux操作系统下,ubuntu22.04版本安装搜狗输入法
  • <PLC><汇川><工控>汇川PLC实现光纤缠绕设备
  • ollama的若干实践