19082 中位特征值

这个问题可以通过深度优先搜索(DFS)和优先队列来解决。我们首先使用DFS来计算每个节点的特征值,然后我们将所有节点的特征值放入一个优先队列中,然后我们从优先队列中取出中间的元素,这就是我们要找的中位数。  以下是C++代码实现:

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;typedef long long ll;
const int MAXN = 1e5 + 5;
vector<int> G[MAXN];
ll V[MAXN], P[MAXN];
int n, T;void dfs(int u, int fa) {P[u] = V[u];for (int i = 0; i < G[u].size(); i++) {int v = G[u][i];if (v == fa) continue;dfs(v, u);P[u] += P[v];}
}int main() {cin >> T >> n;for (int i = 1; i <= n; i++) {cin >> V[i];}for (int i = 1; i < n; i++) {int u, v;cin >> u >> v;G[u].push_back(v);G[v].push_back(u);}dfs(T, 0);vector<ll> values(P + 1, P + n + 1);sort(values.begin(), values.end());cout << values[n / 2] << endl;return 0;
}

在这段代码中,我们首先读取输入的树的根节点T和节点数量n,然后读取每个节点的价值。然后我们读取树的边,对于每条边,我们将它的两个端点加入到对方的邻接列表中。然后我们使用DFS来计算每个节点的特征值。然后我们将所有节点的特征值放入一个数组中,然后对这个数组进行排序。最后,我们输出数组中间的元素,这就是我们要找的中位数。  这段代码的时间复杂度是O(n log n),其中n是节点的数量。因为我们需要对所有节点的特征值进行排序,这个操作的时间复杂度是O(n log n)。然后我们需要遍历所有节点,这个操作的时间复杂度是O(n)。所以总的时间复杂度是O(n log n)。  这段代码的空间复杂度是O(n),因为我们需要存储输入的树和每个节点的特征值。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/387966.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

如何选择合适的自动化测试工具!

选择合适的自动化测试工具是一个涉及多方面因素的决策过程。以下是一些关键步骤和考虑因素&#xff0c;帮助您做出明智的选择&#xff1a; 一、明确测试需求和目标 测试范围&#xff1a;确定需要自动化的测试类型&#xff08;如单元测试、集成测试、UI测试等&#xff09;和测试…

React-Native 宝藏库大揭秘:精选开源项目与实战代码解析

1. 引言 1.1 React-Native 简介 React-Native 是由 Facebook 开发的一个开源框架&#xff0c;它允许开发者使用 JavaScript 和 React 的编程模型来构建跨平台的移动应用。React-Native 的核心理念是“Learn Once, Write Anywhere”&#xff0c;即学习一次 React 的编程模型&am…

社区养老服务小程序的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;用户管理&#xff0c;服务人员管理&#xff0c;服务产品管理&#xff0c;服务预约管理&#xff0c;服务状态管理&#xff0c;服务退订管理&#xff0c;活动管理&#xff0c;视频管理 微信端账号功能包…

基于cubeMX的STM32的RTC实时时钟实现

1、在仪器仪表的项目开发中&#xff0c;时常需要设备显示当前的日期和时间&#xff0c;这时&#xff0c;可以使用STM32自带的RTC实时时钟模块来实现此功能。这里我们使用STM32F103RCT6单片机芯片为例。 2、cubeMX的设置 &#xff08;1&#xff09;RTC设置 &#xff08;2&…

民大食堂用餐小程序的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;用户管理&#xff0c;商家管理&#xff0c;档口号管理&#xff0c;商家餐品管理&#xff0c;餐品种类管理&#xff0c;购物车管理&#xff0c;订单信息管理 微信端账号功能包括&#xff1a;系统首页&a…

yolov10来了!用yolov10训练自己的数据集(原理、训练、部署、应用)

一、引言 YOLOv9还没热乎呢&#xff0c;YOLOv10就出来了&#xff0c;太卷了&#xff01;太快了&#xff01; 自今年2月YOLOv9发布之后&#xff0c; YOLO&#xff08;You Only Look Once&#xff09; 系列的接力棒传到了清华大学研究人员的手上。YOLOv10推出的消息引发了AI界的…

使用 Postman 进行 Trello API 自动化测试的完整指南

文章目录 前言一、自动化测试是什么&#xff1f;二、比较自动化测试与手工测试1. 自动化测试2. 手工测试 三、环境搭建1.创建Collection2.创建环境变量3.添加API请求 四、设计测试用例1. API简单调用2. 获取所有emoji3. 创建一个新看板&#xff1a;4. 获得创建的看板信息5. 在看…

安装nodejs服务器

Java项目可以运行在tomcat服务器&#xff0c;开始完成前后端完全分离。前端有自己独立的工程。我们需要把前端独立的工程运行起来。 运行在nodejs服务器下。 验证是否安装成功&#xff1a;敲cmd--输入node --version 1.安装npm java项目需要依赖jar,安装maven。前端项目也需要依…

Vitis HLS 完美嵌套循环通过 m_axi 接口读取DDR 的迭代次数细粒度控制实验 — 问题描述

1 自媒体账号 目前运营的自媒体账号如下&#xff1a; 哔哩哔哩 【雪天鱼】: 雪天鱼个人主页-bilibili.comCSDN 【雪天鱼】: 雪天鱼-CSDN博客 QQ 学习交流群 FPGA科研硕博交流群 910055563 (进群有一定的学历门槛&#xff0c;长期未发言会被请出群聊&#xff0c;主要交流FPG…

免费!OpenAI发布最新模型GPT-4o mini,取代GPT-3.5,GPT-3.5退出历史舞台?

有个小伙伴问我&#xff0c;GPT-4O mini是什么&#xff0c;当时我还一脸懵逼&#xff0c;便做了一波猜测&#xff1a; 我猜测哈&#xff0c;这个可能是ChatGPT4o的前提下&#xff0c;只支持文本功能的版本&#xff0c;速度更快 结果&#xff0c;大错特错。 让我们一起看看Open…

【简单介绍Gitea】

&#x1f3a5;博主&#xff1a;程序员不想YY啊 &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 ✨希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…

吴恩达老师机器学习-ex4

梯度检测没有实现。有借鉴网上的部分 导入相关库&#xff0c;读取数据 因为这次的数据是mat文件&#xff0c;需要使用scipy库中的loadmat进行读取数据。 通过对数据类型的分析&#xff0c;发现是字典类型&#xff0c;查看该字典的键&#xff0c;可以发现又X&#xff0c;y等关…

类和对象【下】

一、类的默认成员函数 默认成员函数从名字就告诉我们何为默认成员函数&#xff0c;即&#xff1a;用户没有实现&#xff0c;编译器默认自动实现的函数。 这时你不禁一喜&#xff0c;还有这好事&#xff0c;编译器给我打工&#xff0c;那么&#xff0c;我们今天都来了解一下都有…

漏洞复现-路由器TOTOLINK-A6000R-RCE

本文来自无问社区&#xff0c;更多漏洞信息可前往查看http://wwlib.cn/index.php/artread/artid/14996.html 0x01 产品简介 TOTOLINK A6000R是一款性能卓越的无线路由器&#xff0c;采用先进的技术和设计&#xff0c;为用户提供出色的网络体验。其支持最新的Wi-Fi标准&#x…

锅总详解开源组织之ASF

ASF是什么&#xff1f;ASF孵化的顶级项目有哪些&#xff1f;ASF顶级项目商用化有哪些&#xff1f;涉及的版权是什么&#xff1f;应用案例有哪些&#xff1f;衍生项目及其关联是什么&#xff1f;希望本文能帮您解答这些疑惑&#xff01; 一、ASF简介 Apache Software Foundati…

Centos7.6安装Nginx(yum安装和源码安装)

Centos7.6安装Nginx&#xff08;yum安装和源码安装&#xff09; 简介 yum安装 源码安装 安装后的事情 常见问题 简介 Nginx&#xff08;发音为“engine X”&#xff09;是一个高性能的HTTP和反向代理服务器&#xff0c;也可以作为邮件代理服务器使用。它被广泛应用于高流量…

程序员面试中的“八股文”:是助力还是阻力?

“八股文”在实际工作中是助力、阻力还是空谈&#xff1f; 作为现在各类大中小企业面试程序员时的必问内容&#xff0c;“八股文”似乎是很重要的存在。但“八股文”是否能在实际工作中发挥它“敲门砖”应有的作用呢&#xff1f;有IT人士不禁发出疑问&#xff1a;程序员面试考…

使用 ChatGPT 检测媒体偏见的潜力和局限性

概述 随着数字时代的到来&#xff0c;信息瞬间传遍全球&#xff0c;但其中也不乏各种偏见。媒体偏见"&#xff0c;即对某些观点的选择性报道&#xff0c;会影响人们对某一事件或问题的看法&#xff0c;并对公众舆论产生重大影响。事实上&#xff0c;许多人都认为主要媒体…

Data Augmentation数据增强

目录 数据增强是什么 为什么数据增强 数组增强分类 有监督数据增强 无监督数据增强 数据增强是什么 数据增强又称数据扩增&#xff0c;是一种通过应用合理且随机的变换&#xff08;例如图像位移、旋转&#xff09;来增加训练集多样性的技术。让有限的数据产生等价于更多数…

现在有什么赛道可以干到退休?

最近&#xff0c;一则“90后无论男女都得65岁以后退休”的消息在多个网络平台流传&#xff0c;也不知道是真是假&#xff0c;好巧不巧今天刷热点的时候又看到一条这样的热点&#xff1a;现在有什么赛道可以干到退休&#xff1f; 点进去看了几条热评&#xff0c;第一条热评说的…