24年gdcpc省赛C题
1279:DFS 序

先不考虑多节点,先看着颗二叉树,假设他们的父亲节点是第k个被访问的点,如果先访问左子树,那么得到的结果是a1*k+a2*(k+1)+b1*(2+k)+b2*(2+k+1),可以发现,先访问左子树,那么右子树每次的乘以的p值实际上是左子树乘以的p值加上左子树的节点个数,比如a1*k和b1*(2+k),如果不看2,它们同样是第k个被访问的,先访问了a子树,而a子树的节点个数是2,所以再次访问b子树的时候,每一个b子树的节点都加上了2.
那么先访问a子树使得b子树多增加的权值是a子树的节点个数*b子树的权值之和.,同理,先访问b子树那么增加的权值之和是a子树的权值乘以b子树的节点,所以只需要判断是suma*nodeb和sumb*nodea哪一个更大即可.
代码如下
using ll = long long;
struct node {ll num;ll sum;ll node;
};int main() {int n;std::cin >> n;std::vector<node>w(n + 1);for (int i = 1; i <= n; i++) {std::cin >> w[i].sum;w[i].num = w[i].sum;w[i].node = 1;}std::vector<std::vector<ll>>adj(n+1);for (int i = 2; i <= n; i++) {int x;std::cin >> x;adj[x].push_back(i);}auto dfs = [&](auto self,int p)->void {//叶子节点返回if (adj[p].empty())return;//非叶子节点遍历,并累加权值for (auto q : adj[p]) {self(self, q);w[p].sum += w[q].sum;w[p].node += w[q].node;}//排序//sumx*nodey表示先走y,再走x,sumy*nodex,如果先访问y增加的权值大于先访问x增加的权值,那么表达式返回false,交换x,y;std::sort(adj[p].begin(), adj[p].end(), [&](ll x, ll y) {return w[x].sum * w[y].node < w[y].sum * w[x].node;});};dfs(dfs, 1);ll ans = 0,cnt=0;auto bfs = [&](auto self, int p)->void {ans += ++cnt * w[p].num;if (adj[p].empty())return;for (auto q : adj[p]) {self(self, q);}};bfs(bfs, 1);std::cout << ans << '\n';return 0;
}
相关文章:
24年gdcpc省赛C题
1279:DFS 序 先不考虑多节点,先看着颗二叉树,假设他们的父亲节点是第k个被访问的点,如果先访问左子树,那么得到的结果是a1*ka2*(k1)b1*(2k)b2*(2k1),可以发现,先访问左子树,那么右子树每次的乘以的p值实际上是左子树乘以的p值加上左子树的节点个数,比如a1*k和b1*(2k),如果不看2…...
以梦为马,不负韶华(3)-AGI在企业服务的应用
AGI在企业服务中,各应⽤已覆盖企业全流程,包含⼈⼒、法务、财税、流程⾃动化、知识管理和软件开发各领域。 由于⼤语⾔模型对⽂本处理类场景有着天然且直接的适配性,⽂本总结、⽂本内容⽣成、服务指引等发展起步早且应⽤成熟度更⾼。 在数据…...
Xshell 使用
Xshell 使用 ①xshell 安装包 ②xshell 卸载 ③xshell 同时控制多窗口 ①xshell 安装包 Xshell 7 破解版 ②xshell 卸载 第一步: 打开控制面板卸载xshell 第二步: win+R,输入regedit,打开注册表,删除xshell相关注册信息 注册表目录: 在下面两个目录中查找xshell相关…...
【yijiej】mysql报错 之 报错:Duplicate entry 字段 for key ‘表名.idx_字段’
一、问题操作 Mysql 进行insert 操作,报错:Duplicate entry 字段 for key ‘表名.idx_字段’ 原因解析:idx 是做的索引键,是具有唯一性二、问题原因(三种情况,当前我遇到的情况是第一种) 1、当 …...
解决npm卡死,无法安装依赖
npm卡死,无法安装依赖 异常描述原因分析与解决方法 异常描述 1.无法进入命令行,或是很慢没反应 2.装表格无限滚动的el-table-infinite-scroll依赖一上午了,也不能装,报错提示 原因分析与解决方法 1.命令行的问题:缓…...
速卖通测评揭秘:如何选择安全的渠道操作
许多商家对测评存在误解,认为只需进行几次测评就能迅速打造爆款。实际上,测评是一个需要计划和持久性的过程,以便让平台检测到产品的受众程度并提高产品的曝光和权重。 在进行测评时,安全是首要考虑的问题。平台可以通过设备、网…...
ping不通ip的解决方法
解决ping不通IP的问题可以通过以下几种方法: 1.检查IP配置:确保所有设备的IP地址、子网掩码和默认网关配置正确。如果使用DHCP,请确认设备已设置为自动获取IP地址,并检查DHCP服务器的地址池配置是否正确且未耗尽。 2.检查网络设…...
Linux x86_64 UEFI 启动
文章目录 前言一、UEFI二、Disk device compatibility2.1 GPT 磁盘分区表2.1.1 简介2.1.2 Linux 2.2 ESP(EFI) 文件系统2.2.1 简介2.2.2 LinuxLinux Kernel EFI Boot Stub 三、UEFI GPT grub23.1 简介3.2 引导方式 3.3 BOOTX64.EFI3.4 shimx64.efi3.5 …...
妙解设计模式之适配器模式
目录 适配器模式的概念生活中的例子在编程中的例子 软件工程中的实际应用兼容旧接口整合第三方库简化复杂接口跨平台支持 总结 适配器模式的概念 适配器模式是一种结构设计模式,它允许将接口不兼容的类通过一个适配器类进行适配,使得这些类可以一起工作…...
【Linux】Linux下centos更换国内yum源
🌱博客主页:青竹雾色间 🌱系列专栏:Linux 😘博客制作不易欢迎各位👍点赞⭐收藏➕关注 目录 1. 备份旧的 YUM 源文件2. 下载国内的 YUM 源文件阿里云:网易: 3. 清理 YUM 缓存4. 更新…...
HTML静态网页成品作业(HTML+CSS)——动漫熊出没介绍网页(3个页面)
🎉不定期分享源码,关注不丢失哦 文章目录 一、作品介绍二、作品演示三、代码目录四、网站代码HTML部分代码 五、源码获取 一、作品介绍 🏷️本套采用HTMLCSS,未使用Javacsript代码,共有3个页面。 二、作品演示 三、代…...
算法训练营day42
dp含义确定 递推公式 初始化 遍历顺序 打印 题目1:62. 不同路径 - 力扣(LeetCode) class Solution { public:int uniquePaths(int m, int n) {// 定义dp数组 含义是每个坐标到达的路径vector<vector<int>> dp(m, vector&l…...
【Vue】自动导入组件
1. 下载插件 npm install unplugin-vue-components 2. 修改vite.config.js import { fileURLToPath, URL } from node:urlimport { defineConfig } from vite import vue from vitejs/plugin-vue import Components from unplugin-vue-components/vite // 按需加载自定义组件/…...
mfc140u.dll丢失的解决方法有哪些?怎么全面修复mfc140u.dll文件
mfc140u.dll丢失其实相对来说不太常见到,因为这个文件一般是不丢失的,不过既然有人遇到这种问题,那么小编一定满足各位,给大家详细的唠叨一下mfc140u.dll丢失的各种解决方法,教大家以最快最有效率的方法去解决mfc140u.…...
MySQL8报错Public Key Retrieval is not allowedz 怎么解决?
问题描述 当我们使用数据库管理工具连接mysql8的时候,可能遇到报错: Public Key Retrieval is not allowed 解决办法 1、在连接属性中配置allowPublicKeyRetrieval设置为true 2、在连接URL中加上配置allowPublicKeyRetrieval为true...
海外动态IP代理如何提高效率?
动态住宅IP代理之所以能够有效提升数据爬取的效率和准确性,主要归功于其提供的IP地址具有高度的匿名性和真实性。这些IP地址来自于真实的用户网络,因此相比于数据中心IP,它们更不容易被网站的安全系统标识为爬虫。此外,由于IP地址…...
解析边缘计算网关的优势-天拓四方
随着信息化、智能化浪潮的持续推进,计算技术正以前所未有的速度发展,而边缘计算网关作为其中的重要一环,以其独特的优势正在逐步改变我们的生活方式和工作模式。本文将详细解析边缘计算网关的优势。 首先,边缘计算网关具有显著的…...
计算机原理 知识回顾
第一部分:计算机基础概念 计算机的定义 计算机的演化历程计算机的分类(超级计算机、桌面计算机、便携式计算机等) 计算机的基本组成 输入设备、输出设备中央处理单元(CPU)、存储器、主板 计算机的工作原理 数据输…...
WPF 如何调试
简述 它是一种系统机制,用于识别和修复一段代码中的错误或缺陷,这些错误或缺陷的行为与您的预期不同。调试子系统紧密耦合的复杂应用程序并不容易,因为修复一个子系统中的错误可能会在另一个子系统中创建错误。 在 C# 中调试 在 WPF 应用程序…...
URL跳转
1.URL介绍 开放重定向(Open Redirect),也叫URL跳转漏洞,是指服务端未对传入的跳转url变量进行检查和控制,导致诱导用户跳转到恶意网站,由于是从可信的站点跳转出去的,用户会比较信任。 2.URL跳…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...
Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)
引言 在人工智能飞速发展的今天,大语言模型(Large Language Models, LLMs)已成为技术领域的焦点。从智能写作到代码生成,LLM 的应用场景不断扩展,深刻改变了我们的工作和生活方式。然而,理解这些模型的内部…...
【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制
目录 节点的功能承载层(GATT/Adv)局限性: 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能,如 Configuration …...
深度解析:etcd 在 Milvus 向量数据库中的关键作用
目录 🚀 深度解析:etcd 在 Milvus 向量数据库中的关键作用 💡 什么是 etcd? 🧠 Milvus 架构简介 📦 etcd 在 Milvus 中的核心作用 🔧 实际工作流程示意 ⚠️ 如果 etcd 出现问题会怎样&am…...
手动给中文分词和 直接用神经网络RNN做有什么区别
手动分词和基于神经网络(如 RNN)的自动分词在原理、实现方式和效果上有显著差异,以下是核心对比: 1. 实现原理对比 对比维度手动分词(规则 / 词典驱动)神经网络 RNN 分词(数据驱动)…...
