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

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在企业服务中&#xff0c;各应⽤已覆盖企业全流程&#xff0c;包含⼈⼒、法务、财税、流程⾃动化、知识管理和软件开发各领域。 由于⼤语⾔模型对⽂本处理类场景有着天然且直接的适配性&#xff0c;⽂本总结、⽂本内容⽣成、服务指引等发展起步早且应⽤成熟度更⾼。 在数据…...

Xshell 使用

Xshell 使用 ①xshell 安装包 ②xshell 卸载 ③xshell 同时控制多窗口 ①xshell 安装包 Xshell 7 破解版 ②xshell 卸载 第一步: 打开控制面板卸载xshell 第二步: win+R,输入regedit,打开注册表,删除xshell相关注册信息 注册表目录: 在下面两个目录中查找xshell相关…...

【yijiej】mysql报错 之 报错:Duplicate entry 字段 for key ‘表名.idx_字段’

一、问题操作 Mysql 进行insert 操作&#xff0c;报错&#xff1a;Duplicate entry 字段 for key ‘表名.idx_字段’ 原因解析&#xff1a;idx 是做的索引键&#xff0c;是具有唯一性二、问题原因&#xff08;三种情况&#xff0c;当前我遇到的情况是第一种&#xff09; 1、当 …...

解决npm卡死,无法安装依赖

npm卡死&#xff0c;无法安装依赖 异常描述原因分析与解决方法 异常描述 1.无法进入命令行&#xff0c;或是很慢没反应 2.装表格无限滚动的el-table-infinite-scroll依赖一上午了&#xff0c;也不能装&#xff0c;报错提示 原因分析与解决方法 1.命令行的问题&#xff1a;缓…...

速卖通测评揭秘:如何选择安全的渠道操作

许多商家对测评存在误解&#xff0c;认为只需进行几次测评就能迅速打造爆款。实际上&#xff0c;测评是一个需要计划和持久性的过程&#xff0c;以便让平台检测到产品的受众程度并提高产品的曝光和权重。 在进行测评时&#xff0c;安全是首要考虑的问题。平台可以通过设备、网…...

ping不通ip的解决方法

解决ping不通IP的问题可以通过以下几种方法&#xff1a; 1.检查IP配置&#xff1a;确保所有设备的IP地址、子网掩码和默认网关配置正确。如果使用DHCP&#xff0c;请确认设备已设置为自动获取IP地址&#xff0c;并检查DHCP服务器的地址池配置是否正确且未耗尽。 2.检查网络设…...

Linux x86_64 UEFI 启动

文章目录 前言一、UEFI二、Disk device compatibility2.1 GPT 磁盘分区表2.1.1 简介2.1.2 Linux 2.2 ESP&#xff08;EFI&#xff09; 文件系统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 …...

妙解设计模式之适配器模式

目录 适配器模式的概念生活中的例子在编程中的例子 软件工程中的实际应用兼容旧接口整合第三方库简化复杂接口跨平台支持 总结 适配器模式的概念 适配器模式是一种结构设计模式&#xff0c;它允许将接口不兼容的类通过一个适配器类进行适配&#xff0c;使得这些类可以一起工作…...

【Linux】Linux下centos更换国内yum源

&#x1f331;博客主页&#xff1a;青竹雾色间 &#x1f331;系列专栏&#xff1a;Linux &#x1f618;博客制作不易欢迎各位&#x1f44d;点赞⭐收藏➕关注 目录 1. 备份旧的 YUM 源文件2. 下载国内的 YUM 源文件阿里云&#xff1a;网易&#xff1a; 3. 清理 YUM 缓存4. 更新…...

HTML静态网页成品作业(HTML+CSS)——动漫熊出没介绍网页(3个页面)

&#x1f389;不定期分享源码&#xff0c;关注不丢失哦 文章目录 一、作品介绍二、作品演示三、代码目录四、网站代码HTML部分代码 五、源码获取 一、作品介绍 &#x1f3f7;️本套采用HTMLCSS&#xff0c;未使用Javacsript代码&#xff0c;共有3个页面。 二、作品演示 三、代…...

算法训练营day42

dp含义确定 递推公式 初始化 遍历顺序 打印 题目1&#xff1a;62. 不同路径 - 力扣&#xff08;LeetCode&#xff09; 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丢失其实相对来说不太常见到&#xff0c;因为这个文件一般是不丢失的&#xff0c;不过既然有人遇到这种问题&#xff0c;那么小编一定满足各位&#xff0c;给大家详细的唠叨一下mfc140u.dll丢失的各种解决方法&#xff0c;教大家以最快最有效率的方法去解决mfc140u.…...

MySQL8报错Public Key Retrieval is not allowedz 怎么解决?

问题描述 当我们使用数据库管理工具连接mysql8的时候&#xff0c;可能遇到报错&#xff1a; Public Key Retrieval is not allowed 解决办法 1、在连接属性中配置allowPublicKeyRetrieval设置为true 2、在连接URL中加上配置allowPublicKeyRetrieval为true...

海外动态IP代理如何提高效率?

动态住宅IP代理之所以能够有效提升数据爬取的效率和准确性&#xff0c;主要归功于其提供的IP地址具有高度的匿名性和真实性。这些IP地址来自于真实的用户网络&#xff0c;因此相比于数据中心IP&#xff0c;它们更不容易被网站的安全系统标识为爬虫。此外&#xff0c;由于IP地址…...

解析边缘计算网关的优势-天拓四方

随着信息化、智能化浪潮的持续推进&#xff0c;计算技术正以前所未有的速度发展&#xff0c;而边缘计算网关作为其中的重要一环&#xff0c;以其独特的优势正在逐步改变我们的生活方式和工作模式。本文将详细解析边缘计算网关的优势。 首先&#xff0c;边缘计算网关具有显著的…...

计算机原理 知识回顾

第一部分&#xff1a;计算机基础概念 计算机的定义 计算机的演化历程计算机的分类&#xff08;超级计算机、桌面计算机、便携式计算机等&#xff09; 计算机的基本组成 输入设备、输出设备中央处理单元&#xff08;CPU&#xff09;、存储器、主板 计算机的工作原理 数据输…...

WPF 如何调试

简述 它是一种系统机制&#xff0c;用于识别和修复一段代码中的错误或缺陷&#xff0c;这些错误或缺陷的行为与您的预期不同。调试子系统紧密耦合的复杂应用程序并不容易&#xff0c;因为修复一个子系统中的错误可能会在另一个子系统中创建错误。 在 C# 中调试 在 WPF 应用程序…...

URL跳转

1.URL介绍 开放重定向&#xff08;Open Redirect&#xff09;&#xff0c;也叫URL跳转漏洞&#xff0c;是指服务端未对传入的跳转url变量进行检查和控制&#xff0c;导致诱导用户跳转到恶意网站&#xff0c;由于是从可信的站点跳转出去的&#xff0c;用户会比较信任。 2.URL跳…...

OpenClaw语音交互:Phi-3-mini接入麦克风输入实战

OpenClaw语音交互&#xff1a;Phi-3-mini接入麦克风输入实战 1. 为什么需要语音交互能力 上周我在整理电脑文件时突然想到一个问题&#xff1a;当我的双手被占用时&#xff08;比如正在做饭或修理设备&#xff09;&#xff0c;如何让OpenClaw帮我执行任务&#xff1f;传统的键…...

OpenClaw自动化视频处理:Qwen2.5-VL-7B分析关键帧生成视频摘要

OpenClaw自动化视频处理&#xff1a;Qwen2.5-VL-7B分析关键帧生成视频摘要 1. 为什么需要自动化视频摘要 作为一个经常需要处理大量视频素材的自媒体创作者&#xff0c;我长期被一个痛点困扰&#xff1a;如何快速了解长视频的核心内容。传统方法要么是手动拖动进度条随机查看…...

seo 站群的优缺点是什么

SEO 站群的优缺点解析 在现代的互联网营销中&#xff0c;SEO&#xff08;搜索引擎优化&#xff09;站群是一个重要的概念。SEO 站群是指由多个主题相关的网站组成的集合&#xff0c;这些网站通过某种联系形式运作在一起&#xff0c;以提升整体的搜索引擎排名和流量。虽然 SEO …...

【Polars 2.0企业级数据清洗黄金法则】:5大生产环境避坑指南+实测性能提升3.7倍基准报告

第一章&#xff1a;Polars 2.0企业级数据清洗黄金法则总览Polars 2.0 以零拷贝语义、并行执行引擎与原生 Arrow 内存布局为核心&#xff0c;重构了企业级数据清洗的性能边界与工程可靠性。其惰性 API 与 eager 模式无缝协同&#xff0c;使复杂清洗流水线既可交互调试&#xff0…...

基于Wan 3D Causal VAE(Show-o2)的模型,重新完整地分析 10分钟的视频 对应多少 vison token

可以。这次我按 Show-o2 官方 432432 配置 和 Wan 3D Causal VAE 的公开时间压缩规则,把 10B token 且全部都是 vision token 的情况重新完整算一遍。下面的“大小”我统一按 未压缩 RGB 原始数据量 来算;如果你问的是实际 JPG / PNG / MP4 落盘大小,那会随压缩格式、码率和…...

2026年4月OpenClaw如何安装?腾讯云2分钟零基础教程及百炼APIKey配置方法

2026年4月OpenClaw如何安装&#xff1f;腾讯云2分钟零基础教程及百炼APIKey配置方法。OpenClaw&#xff08;原Clawdbot&#xff09;作为2026年主流的AI自动化助理平台&#xff0c;可通过阿里云轻量服务器实现724小时稳定运行&#xff0c;并快速接入钉钉&#xff0c;让AI在企业群…...

MotorController:嵌入式伺服电机驱动的确定性执行封装

1. 项目概述MotorController是一个面向伺服系统电机控制的轻量级工具类&#xff0c;其设计目标并非替代完整的运动控制固件栈&#xff0c;而是为嵌入式工程师提供一套可直接集成、低侵入、高可控性的底层电机驱动封装。该类不依赖特定硬件抽象层&#xff08;HAL&#xff09;或实…...

Fiji图像处理软件更新故障排查指南:当科学工具遇到“升级烦恼“

Fiji图像处理软件更新故障排查指南&#xff1a;当科学工具遇到"升级烦恼" 【免费下载链接】fiji A "batteries-included" distribution of ImageJ :battery: 项目地址: https://gitcode.com/gh_mirrors/fi/fiji Fiji作为生物图像分析领域的瑞士军刀…...

SDMatte部署避坑指南:首次加载延迟、模型切换等待、端口冲突解决方案

SDMatte部署避坑指南&#xff1a;首次加载延迟、模型切换等待、端口冲突解决方案 1. 为什么选择SDMatte进行图像抠图 SDMatte是一款专为高质量图像抠图设计的AI模型&#xff0c;特别适合处理那些传统抠图工具难以应对的复杂场景。想象一下&#xff0c;你需要把玻璃杯从背景中…...

从拆解到驱动:手把手教你用IMX6ULL驱动OV5640摄像头模块(附完整代码)

从拆解到驱动&#xff1a;手把手教你用IMX6ULL驱动OV5640摄像头模块&#xff08;附完整代码&#xff09; 1. 硬件连接与接口解析 OV5640作为一款500万像素的CMOS图像传感器&#xff0c;支持DVP和MIPI两种接口模式。在IMX6ULL平台上&#xff0c;我们选择使用DVP并行接口进行连接…...