cf168(div2):D.Maximize the Root(树)

news/2024/12/23 3:22:39/

题目

给你一棵有根的树,由 𝑛n 个顶点组成。树中的顶点编号为 11 至 𝑛n ,根顶点为 11 。值 𝑎𝑖ai 写在第 𝑖i 个顶点上。

您可以执行以下任意次数(可能为零)的操作:选择一个顶点 𝑣v **该顶点至少有一个子顶点。至少有一个子顶点;将 𝑎𝑣av 增加 11 ;并将 𝑎𝑢au 减少 11 ,所有顶点 𝑢u 都在 𝑣v 的子树中( 𝑣v 本身除外)。但是,每次操作后,所有顶点上的值都应该是非负值。

您的任务是通过上述操作计算出写入根的最大可能值。

输入

第一行包含一个整数 𝑡t ( 1≤𝑡≤1041≤t≤104 ) - 测试用例数。

每个测试用例的第一行包含一个整数 𝑛n ( 2≤𝑛≤2⋅1052≤n≤2⋅105 ) - 树中顶点的数量。

第二行包含 𝑛n 个整数 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an ( 0≤𝑎𝑖≤1090≤ai≤109 ) - 写入顶点的初始值。

第三行包含 𝑛−1n−1 个整数 𝑝2,𝑝3,…,𝑝𝑛p2,p3,…,pn ( 1≤𝑝𝑖≤𝑛1≤pi≤n ),其中 𝑝𝑖pi 是树中第 𝑖i 个顶点的父节点。顶点 11 是根。

输入的附加限制:所有测试用例中 𝑛n 的总和不超过 2⋅1052⋅105 。

输出

对于每个测试用例,打印一个整数--使用上述操作在根处写入的最大可能值。

做法

#include<bits/stdc++.h> 
using namespace std;int t,n;
long long a[200010];
vector<int> g[200010];void dfs(int x){long long mi=1e9+10;for(auto y:g[x]){dfs(y);mi=min(mi,a[y]);//子树的最小值}if(mi!=1e9+10){ //底部值不变 (没有子树) if(mi>a[x]){a[x]=(mi+a[x])/2;///最多增加}else a[x]=mi;//最多增加}
}
int main(){cin>>t;while(t--){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);for(int i=2;i<=n;i++){int p;scanf("%d",&p);g[p].push_back(i);}long long f=a[1];dfs(1);long long mi=2e9+10;for(auto x: g[1]){mi=min(mi,a[x]);//最多能增加的值}cout<<mi+f<<endl;for(int i=1;i<=n;i++) g[i].clear();}
}


http://www.ppmy.cn/news/1503559.html

相关文章

黑马JavaWeb后端案例开发(包含所有知识点!!!)

目录 1.准备工作 环境搭建 开发规范 REST&#xff08;REpresentation State Transfer&#xff09;,表述性状态转换&#xff0c;它是一种软件架构风格 注意事项 统一响应结果 2.部门管理功能 查询部门 删除部门 新增部门 RequestMapping 3.员工管理功能 分页查询 批…

『 Linux 』基于阻塞队列的生产者消费者模型

文章目录 生产者-消费者模型概述生产者消费者模型的高效性虚假唤醒信号丢失生产者消费者模型的模拟实现参考代码 生产者-消费者模型概述 生产者消费者模型是一种多线程设计模式,常见于解决多个生产者线程和多个消费者线程之间如何安全有效地共享数据; 该模型中存在三种关系,两个…

传统自然语言处理(NLP)与大规模语言模型(LLM)详解

自然语言处理&#xff08;NLP&#xff09;和大规模语言模型&#xff08;LLM&#xff09;是理解和生成人类语言的两种主要方法。本文将介绍传统NLP和LLM的介绍、运行步骤以及它们之间的比较&#xff0c;帮助新手了解这两个领域的基础知识。 传统自然语言处理&#xff08;NLP&…

JavaScript异步编程的Promise

目录 1.对Promise的了解 &#xff08;1&#xff09;介绍 &#xff08;2&#xff09;Promise 的优缺点 2.Promise的基本用法 &#xff08;1&#xff09;创建Promise对象 &#xff08;2&#xff09;Promise方法then() &#xff08;3&#xff09;Promise方法catch() &…

C语言实现三子棋

通过一段时间的学习&#xff0c;我们已经能够较为熟练地使用分支语句&#xff0c;循环语句&#xff0c;创建函数&#xff0c;创建数组&#xff0c;创建随机数等。之前我们做过一个扫雷游戏&#xff0c;今天让我们再尝试创作一个三子棋游戏吧~ 一、三子棋游戏的思路 三子棋的游…

语音交互、AI问答,等你来体验!

功能背景 在实际大屏应用中&#xff0c;用户向大屏直接下达语音指令显的越来越便捷&#xff0c;其中体现的交互感也比通过动作指令来的更加强烈&#xff0c;给用户带来更高效的服务体验。目前EasyV平台开发的自定义事件交互已经很完善&#xff0c;组件之间可以进行触发联动。 …

Spring Boot集成udp通讯

Spring Boot集成udp通讯 加入依赖编辑配置文件配置相关属性具体业务类客户端调试 加入依赖 <!--加入UDP通信所需依赖--><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-integration</artifactId&…

Spring Security 概述,鸟瞰 Spring Security 及其功能

在本文中&#xff0c;我们将从鸟瞰的角度了解 Spring Security 的用途以及它能为我们提供什么。网络上的任何东西都可能是攻击的潜在受害者。不幸的是&#xff0c;在这个即使是最富有、最具创新性的技术公司也会受到黑客攻击的世界里&#xff0c;保护 Web 应用程序并实现授权和…