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

CF1120 D. Power Tree 巧妙的图论转化

传送门

[前题提要]:无

题目描述:

就是给你一棵树,然后每个点有花费,然后你可以选一个点,付费后对这个点的子树的所有叶子结点增减任意权值.
考虑有一个人会给这棵树的所有叶子结点赋值(值我们不知道),输出最小的花费,使得无论它如何赋值,我们使用上述的花
费都能使所有的叶子节点变为0

考虑对一个点的子树的所有叶子节点进行增减任意值.不难联想到对一个点的子树的所有节点增减任意值的做法.所以考虑使用类似于树链剖分的方式将树上修改化为链上区间修改.
考虑记录一个点的所有叶子节点,并且按照 d f s dfs dfs序将其离散化存下.按照 d f s dfs dfs序的性质,我们会发现一个点的所有叶子节点必然是连续的区间.那么此时我们的问题就变成了:
给你 n n n个可以修改的区间,每一个区间都有其修改范围,修改每一个区间需要一定花费,问你至少需要多少花费将所有数字变为0
考虑到区间修改以及单点查询,我们想到使用差分来解决.假设我们使用一个差分数组 k [ i ] = a [ i ] − a [ i − 1 ] k[i]=a[i]-a[i-1] k[i]=a[i]a[i1],那么对于每一次区间修改来说,我们都是 a [ l ] + = v a l , a [ r + 1 ] − = v a l a[l]+=val,a[r+1]-=val a[l]+=val,a[r+1]=val,那么最终我们需要得到的所有的 k [ i ] = = 0 k[i]==0 k[i]==0.
此时有一个巧妙的转化,考虑我们需要所有的k[i]变为0,但是显然我们的差分数组是不改变前缀和的,所以此时所有的值肯定都转移到了cnt+1的位置(假设我们有cnt个叶子节点),那么对于我们的数的转移来说,我们只能将 l l l转移到 r + 1 r+1 r+1,如果我们将转移过程看成边,将每一个叶子结点看成点,那么我们想将所有的值都转移到 c n t + 1 cnt+1 cnt+1,就需要所有的点都联通才行,这样才能保证无论怎么赋值我们都可以将其转移到 c n t + 1 cnt+1 cnt+1的位置
那么此时这道题就简单了,考虑到必须所有点都联通,每次选择联通一个点我们都需要花费,又需要花费最小,所以显然是个最小生成树的模型,此时使用最小生成树跑一下就行.

但是还有一个问题,那就是这道题的最终问题是所有的可能性的最小生成树的点,所以我们用朴素的 k r u s k a l kruskal kruskal跑出来的只是一棵树,需要改一下.考虑到最小生成树的性质,当边相同时,我们可以选择任意一条不在联通块中的边,所以这些边显然都是平等的,所以这些边都是我们的答案(当然这一点是可以严谨证明的,但是限于篇幅,此处不再赘述)


下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
inline void print(__int128 x){if(x<0) {putchar('-');x=-x;}if(x>9) print(x/10);putchar(x%10+'0');
}
#define maxn 1000000
#define int long long
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int w[maxn];vector<int>edge[maxn];int l[maxn],r[maxn];
int cnt=0;
void dfs(int u,int per_u) {if(edge[u].size()==1&&u!=1) {++cnt;l[u]=r[u]=cnt;}for(auto v:edge[u]) {if(v==per_u) continue;dfs(v,u);l[u]=min(l[u],l[v]);r[u]=max(r[u],r[v]);}
}
struct Edge{int u,v,w,id;bool operator < (const Edge &rhs) const {return w<rhs.w;}
}edge2[maxn];
int fa[maxn];
int find(int x) {if(x==fa[x]) return x;else return fa[x]=find(fa[x]);
}
signed main() {int n=read();for(int i=1;i<=n;i++) {w[i]=read();}for(int i=1;i<n;i++) {int u=read();int v=read();edge[u].push_back(v);edge[v].push_back(u);}memset(l,0x3f,sizeof l);memset(r,-0x3f,sizeof r);dfs(1,0);for(int i=1;i<=n;i++) {int u=l[i],v=r[i];edge2[i]={u,v+1,w[i],i};}for(int i=1;i<=cnt;i++) fa[i]=i;sort(edge2+1,edge2+1+n);vector<int>ans;int this_cnt=0;int need=0;for(int i=1;i<=n;i++) {int r=i;while(r+1<=n&&edge2[r+1].w==edge2[r].w) r++;for(int j=i;j<=r;j++) {auto [u,v,w,k]=edge2[j];if(find(u)!=find(v)) {this_cnt++;ans.push_back(k);}}for(int j=i;j<=r;j++) {auto [u,v,w,k]=edge2[j];if(find(u)!=find(v)) {need+=w;fa[find(u)]=find(v);}}i=r;}sort(ans.begin(),ans.end());cout<<need<<" "<<ans.size()<<endl;for(auto i:ans) cout<<i<<" ";return 0;
}

相关文章:

CF1120 D. Power Tree 巧妙的图论转化

传送门 [前题提要]:无 题目描述: 就是给你一棵树,然后每个点有花费,然后你可以选一个点,付费后对这个点的子树的所有叶子结点增减任意权值. 考虑有一个人会给这棵树的所有叶子结点赋值(值我们不知道),输出最小的花费,使得无论它如何赋值,我们使用上述的花 费都能使所有的叶子…...

【算法训练-字符串 三】最长公共子串、最长公共子序列

废话不多说&#xff0c;喊一句号子鼓励自己&#xff1a;程序员永不失业&#xff0c;程序员走向架构&#xff01;本篇Blog的主题是【】&#xff0c;使用【】这个基本的数据结构来实现&#xff0c;这个高频题的站点是&#xff1a;CodeTop&#xff0c;筛选条件为&#xff1a;目标公…...

lintcode 1446 · 01矩阵走路问题 【两次BFS, VIP 中等 1也计算距离,但是不入队列】

题目链接&#xff0c;描述 https://www.lintcode.com/problem/1446 给定一个大小为 n*m 的 01 矩阵 grid &#xff0c;1 是墙&#xff0c;0 是路&#xff0c;你现在可以把 grid 中的一个 1 变成 0&#xff0c;请问从左上角走到右下角是否有路可走&#xff1f;如果有路可走&am…...

第一个实例:QT实现汽车电子仪表盘

目录 1.实现效果 1.1.视频演示 1.2.实现效果截图 2.生成的安装程序 3.功能概述 4.具体实现 5.QT扩展介绍 5.1.QT介绍 5.2.QT历史发展 5.3.QT平台支持 5.4.Qt Creator 5.5.优势 5.5.1.优良的跨平台特性 5.5.2.面向对象 5.5.3.丰富的 API 1.实现效果 1.1.视频演…...

【MySQL系列】MySQL的事务管理的学习(一)_ 事务概念 | 事务操作方式 | 事务隔离级别

「前言」文章内容大致是MySQL事务管理。 「归属专栏」MySQL 「主页链接」个人主页 「笔者」枫叶先生(fy) 目录 一、事务概念二、事务的版本支持三、事务提交方式四、事务常见的操作方式4.1 事务正常操作4.2 事务异常验证 五、事务隔离级别5.1 查看与设置隔离性5.2 读未提交&…...

扫地机器人还能创新吗?云鲸给了个Yes

作者 | 辰纹 来源 | 洞见新研社 1996年&#xff0c;瑞典家电巨头伊莱克斯推出全球首款扫地机器人“三叶虫”。 与现在的产品相比&#xff0c;“三叶虫”靠随机碰撞的模式对空间进行清扫&#xff0c;清洁效率很低&#xff0c;市场渗透率也不高&#xff0c;但并不妨碍戴森、iRo…...

PHP NBA球迷俱乐部系统Dreamweaver开发mysql数据库web结构php编程计算机网页

一、源码特点 PHP NBA球迷俱乐部系统是一套完善的web设计系统&#xff0c;对理解php编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。 基于PHP的NBA球迷俱乐部 二、功能介绍 1、前台主要功能&#xff1a; 系统首页 网站介…...

JavaScript-----DOM元素

目录 前言&#xff1a; 1. DOM介绍 2. 获取节点 3. 操作HTML内容 4. 监听事件 案例 5. 操作节点的标签属性 6. 操作样式 7. 创建、添加、删除节点 前言&#xff1a; 在此之前我们要想去操作网页元素一般是去通过CSS选择器实现的&#xff0c;今天我们就学习JavaScript里…...

激光切割机在船舶行业的的应用有哪些

我国享有世界工厂的美誉&#xff0c;是全球制造业的主力。然而&#xff0c;在船舶制造的关键技术领域&#xff0c;我国的研发投入不足&#xff0c;技术进步仍滞后&#xff0c;我国高端船舶制造的实力仍显不足。 在我国制造业全面复苏的当前背景下&#xff0c;“精准制作”正构成…...

AFL++模糊测试

一、AFL 这里我们主要使用AFL Fuzzing 测试IOT的二进制文件&#xff0c;当我们解压提取一个固件时&#xff0c;能够获得大量的IOT二进制应用 &#xff0c;如果要进行漏洞挖掘则需要将二进制文件进行逆向分析&#xff0c;然后查找危险函数以及输入接口&#xff0c;对于一个大型的…...

C# 使用ListBox及Picturebox显示所选的任意路径文件夹下的图像

using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System...

数据库: 存储过程

sql server begin end用法: SQL Server中的BEGIN END用法是用于定义一个代码块&#xff0c;这个代码块可以包含多个SQL语句&#xff0c;BEGIN END通常用于控制流程语句&#xff0c;例如IF语句、WHILE语句、TRY CATCH语句等。在BEGIN END代码块中&#xff0c;可以使用变量、函数…...

【juc】ReentrantReadWriteLock之缓存(仅当学习)

目录 一、说明二、代码示例2.1 pom依赖2.2 示例代码2.3 实体类 三、示例截图 一、说明 1.针对于读多写少的情况 2.先查缓存&#xff0c;没有再去查库 二、代码示例 2.1 pom依赖 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"h…...

FLUX查询InfluxDB -- InfluxDB笔记三

1. 入门 from(bucket: "example_query") // 没有筛选条件直接查询会报错|> range(start: -1h) // |>是管道符&#xff0c;后跟筛选条件 2. 序列、表和表流 序列是InfluxDB的概念&#xff0c;一个序列是由measurement、标签集、一个字段名称 表流是FLUX为了…...

pico学习进程记录已经开发项目

Pico pin脚定义 Pico 运行准备 下载uf2文件 https://pico.org.cn/ &#xff08;注意运行micropython的文件和运行c/c的不一样&#xff09; 装载uf2文件&#xff1a;按住pico的按键&#xff0c;然后通过micro usb连接电脑&#xff08;注意&#xff1a;如果用的线材&#xff0c…...

C++(20):多重继承与虚继承

多重继承 是指从多个直接基类中产生派生类的能力。多重继承的派生类继承了所有父类的属性。 多重继承 在派生类的派生列表中可以包含多个基类&#xff1a; class Bear : public zooAnimal { class Panda : public Bear, public Endangered{/* ...*/};每个基类包含一个可选的…...

Vue + Element UI 前端篇(一):搭建开发环境

Vue Element UI 实现权限管理系统 前端篇&#xff08;一&#xff09;&#xff1a;搭建开发环境 技术基础 开发之前&#xff0c;请先熟悉下面的4个文档 vue.js2.0中文, 优秀的JS框架vue-router, vue.js 配套路由vuex&#xff0c;vue.js 应用状态管理库Element&#xff0c;饿…...

系统错误码指示确立+日志模块手动配置

1&#xff0c;系统错误码指示确立 对于前后端分离的系统设计中&#xff0c;后端建立错误码指示对于前端非常重要可以指示错误存在地方&#xff1b;以用户注册为例&#xff1b; public interface SystemCode{int SYSTEM_USER_ERROR_ADD_FAIL 10000;int SYSTEM_USER_INFO_ADD …...

Java入门第三季

一、异常与异常处理 1. 异常简介 在Java中&#xff0c;**异常是程序在执行过程中出现的问题或意外情况&#xff0c;导致程序无法按照预期的流程进行。**异常处理是Java中用于处理程序中出现的异常的一种机制。 Java中的异常可以分为两大类&#xff1a;受检查的异常&#xff…...

【linux命令讲解大全】056.updatedb命令:创建或更新slocate数据库文件

文章目录 updatedb补充说明语法选项实例 从零学 python updatedb 创建或更新slocate命令所必需的数据库文件 补充说明 updatedb命令用来创建或更新slocate命令所必需的数据库文件。updatedb命令的执行过程较长&#xff0c;因为在执行时它会遍历整个系统的目录树&#xff0c;…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...

《Docker》架构

文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器&#xff0c;docker&#xff0c;镜像&#xff0c;k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现指南针功能

指南针功能是许多位置服务应用的基础功能之一。下面我将详细介绍如何在HarmonyOS 5中使用DevEco Studio实现指南针功能。 1. 开发环境准备 确保已安装DevEco Studio 3.1或更高版本确保项目使用的是HarmonyOS 5.0 SDK在项目的module.json5中配置必要的权限 2. 权限配置 在mo…...

篇章二 论坛系统——系统设计

目录 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 1. 数据库设计 1.1 数据库名: forum db 1.2 表的设计 1.3 编写SQL 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 通过需求分析获得概念类并结合业务实现过程中的技术需要&#x…...

向量几何的二元性:叉乘模长与内积投影的深层联系

在数学与物理的空间世界中&#xff0c;向量运算构成了理解几何结构的基石。叉乘&#xff08;外积&#xff09;与点积&#xff08;内积&#xff09;作为向量代数的两大支柱&#xff0c;表面上呈现出截然不同的几何意义与代数形式&#xff0c;却在深层次上揭示了向量间相互作用的…...