动态规划(算法竞赛、蓝桥杯)--树形DP树的中心

1、B站视频链接:E34 树形DP 树的中心_哔哩哔哩_bilibili

6355ff2a9bf84456883a6bdee6713a15.png

f8407fe676ab47b88501146139df0c6e.png

33d3614356944a838c809e6e105e4776.png

22dd4c8341494baa939feb670d7d7e8c.png

3a336152c2df42d697142a851663354f.png

#include <bits/stdc++.h> 
using namespace std;
const int N=20010;
int n,a,b,c,ans=2e9;
struct edge{int v,w;};
vector<edge> e[N];
int d1[N],d2[N],path[N],up[N];//path记录d1 

void dfs1(int x,int fa){
	for(auto ed:e[x]){
		int y=ed.v,z=ed.w;
		if(y==fa)continue;
		dfs1(y,x);
		if(d1[y]+z>d1[x]){
			d2[x]=d1[x],d1[x]=d1[y]+z,path[x]=y;
		}else if(d1[y]+z>d2[x])d2[x]=d1[y]+z;
	}
}
void dfs2(int x,int fa){
	for(auto ed:e[x]){
		int y=ed.v,z=ed.w;
		if(y==fa)continue;
		if(y==path[x])up[y]=max(up[x],d2[x])+z;
		else up[y]=max(up[x],d1[x])+z;
		dfs2(y,x);
	}
}
int main(){
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>a>>b>>c;
		e[a].push_back({b,c});
		e[b].push_back({a,c});
	}
	dfs1(1,0);//向下 
	dfs2(1,0);//向上 
	for(int i=1;i<=n;i++){
		ans=min(ans,max(d1[i],up[i]));
	}
	cout<<ans;
	return 0;
}

3b59cf6325fc4a5289582f24f50f7a37.png

 

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Vue】sessionStorage存取数据

一. 需求 1.1 模板 Vab Admin Pro 1.2 组件 ElementUI 1.3 阐述 列表页面搜索【关键词】点击【查询】后&#xff0c;点击【查看】按钮跳转到【详情页】&#xff0c;详情页【返回】【保留原搜索关键词】 原图 搜索查询【关键词】 详情 返回后【保留】【搜索查询关键词…

潜水耳机哪个牌子好?认准这几个游泳耳机品牌就对了!

在科技日益发达的今天&#xff0c;人们对于运动设备的需求也在不断提升。作为一项独特的水上运动&#xff0c;潜水爱好者们对耳机的要求也越来越高。一款优秀的潜水耳机不仅能够提供卓越的防水性能和舒适度&#xff0c;还必须具备出色的音质。那么&#xff0c;在众多品牌中&…

2024宠物行业未来发展趋势:京东宠物健康(宠物营养保健和医疗)市场品类数据分析报告

近段时间&#xff0c;广州某知名宠物医院的医疗事故正在被大众热议&#xff0c;也让越来越多从业者开始关心宠物医疗行业的未来形势。 在2022年下半年&#xff0c;京东平台专门设立了一个一级大类目&#xff1a;宠物健康&#xff08;将其从原本的宠物生活类目中独立出来&#…

【C++】c++入门之递归上 数值类

文章目录 前言一、 递归1.1 基本概念1.2 递归的过程1.3 使用场景 二、例题讲解问题一&#xff1a;1002 - 编程求解123...n问题二&#xff1a;1241 - 角谷猜想问题三&#xff1a;1108 - 正整数N转换成一个二进制数问题四&#xff1a;1088 - 求两个数M和N的最大公约数 三、练习问…

Chrome禁止自动升级

一、关闭计划任务 1、首先我们需要右键点击我的电脑&#xff0c;在打开的选项里选择管理。   2、在打开的对话框中选择任务计划程序。   3、在任务计划程序库中找到两个和chrome自动更新相关的任务计划GoogleUpdateTaskMachineCore与GoogleUpdateTaskMachineUA。     4…

onlyOffice-windows 安装说明(二)

onlyoffice windows 安装 onlyoffice 支持多个平台比如&#xff1a;Windows Server、Linux、Docker 以下内容是对官网安装说明做了简单翻译&#xff0c;仅供参考&#xff0c;原文链接地址参见文末。 社区版允许您在本地服务器上安装ONLYOFFICE文档&#xff0c;并将在线编辑器…

【李沐精读系列】BERT精读

论文&#xff1a;BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding 参考&#xff1a;BERT论文逐段精读、李沐精读系列、李宏毅版BERT讲解 一、介绍 BERT(Bidirectional EncoderRepresentation Transformer&#xff0c;双向Transformer编码器…

JAVA 用二分法查找数组中是否存在某个值

二分法查找的概念 二分查找也称折半查找&#xff08;Binary Search&#xff09;&#xff0c;它是一种效率较高的查找方法。首先&#xff0c;将表中间位置记录的关键字与查找关键字比较&#xff0c;如果两者相等&#xff0c;则查找成功&#xff1b;否则利用中间位置记录将表分成…

pinia报错does not provide an export named ‘hasInjectionContext

你们好&#xff0c;我是金金金。 场景 我这里是uniappvue3编写的一个小程序项目&#xff0c;在集成pinia过程当中遇到此问题&#xff0c;报错请求的模块 未提供 导出名hasInjectionContext&#xff08;位于 pinia.mjs:6:10&#xff09; 以下我项目当中vue和pinia的具体依赖版本…

selenium等待机制

selenium等待机制 影响元素加载的外部因素1.计算机的性能2.服务器的性能3.浏览器的性能4.网络因素 强制等待1.强制等待2.页面加载超时机制 隐性等待显性等待1.WebDriverWait类2.WebDriverWait类提供的方法untileuntile_not显性等待的语法格式 3.expected_conditions模块方法exp…

「Mybatis深入三」:高级查询-模糊查询

一、需求 根据username 模糊查询user 表 二、代码演示 1、方式1 数据库环境 CREATE DATABASE mybatis_db; USE mybatis_db; CREATE TABLE user (id INT(11) NOT NULL AUTO_INCREMENT,username VARCHAR(32) NOT NULL COMMENT 用户名称,birthday DATETIME DEFAULT NULL COMMEN…

Java开发从入门到精通(一):Java的基础语法进阶

Java大数据开发和安全开发 &#xff08;一&#xff09;Java注释符1.1 单行注释 //1.2 多行注释 /* */1.3 文档注释 /** */1.4 各种注释区别1.5 注释的特点1.5 注释的快捷键 &#xff08;二&#xff09;Java的字面量&#xff08;三&#xff09;Java的变量3.1 认识变量3.2 为什么…

【宏观经济】全国各地级市及上市公司“信息惠民国家试点”DID(2010-2024)

数据说明&#xff1a;信息惠民国家试点城市是&#xff0c;2014年6月23日&#xff0c;根据国家发改委网站发布的通知&#xff0c;国家发展改革委等12部门决定的&#xff0c;将全国80个城市列为信息惠民国家试点城市。推进信息惠民国家试点城市建设&#xff0c;有利于加快提升公共…

vue+Nodejs+Koa搭建前后端系统(九)-- 上传图片

web2.0的到来使网页世界正式进入了寒武纪&#xff0c;各式各样的多媒体资源屡见不鲜&#xff0c;上传资源变得刻不容缓&#xff01; 前言 本文是在该系列的基础上&#xff0c;针对前后端代码的修改。 准备 HTTP上传图片时Content-Type值常见的有2种&#xff1a;application…

Django模型层(附带test环境)

Django模型层(附带test环境) 目录 Django模型层(附带test环境)开启测试环境数据的增加数据的删除修改数据查询数据查询所有数据去重查询排序查询统计剔除指定数据多表查询校验数据是否存在字段的筛选查询 开启测试环境 首先在app下找到tests.py文件并进入 MyDJ.settings要换成…

【QA-SYSTEMS】CANTATA-解决Jenkins中build Cantata报错

【更多软件使用问题请点击亿道电子官方网站查询】 1、 文档目标 解决Jenkins中build Cantata测试项目报找不到license server的错误。 2、 问题场景 在Jenkins中build Cantata测试项目&#xff0c;报错“Failed to figure out the license server correctly”。 3、软硬件环…

虚拟化相关面试题集锦(0)—— 引言

经常关注博主的朋友应该能够发现&#xff0c;我近期开始在虚拟化尤其是QEMU/KVM上下功夫。这是由于我个人非常看好这个方向&#xff0c;把它当作今后的学习和工作的战略目标&#xff0c;同时也是个人非常喜欢和感兴趣的课题。 笔者看好虚拟化的原因是当前云计算已经如日中天&a…

短视频矩阵系统----矩阵系统源码搭建(技术门槛?)

短视频矩阵是什么意思&#xff1f;短视频矩阵的含义可以理解为全方位的短视频账号&#xff0c;通过不同的账号实现全方位的品牌展示。实际上是指一个短视频账号&#xff0c;通过不同的链接实现品牌展示&#xff0c;在不同的粉丝流量账号中互相转发同一个品牌&#xff0c;在主账…

05 | 深入浅出索引(下)

在上一篇文章中&#xff0c;我和你介绍了 InnoDB 索引的数据结构模型&#xff0c;今天我们再继续聊聊跟 MySQL 索引有关的概念。 在开始这篇文章之前&#xff0c;我们先来看一下这个问题&#xff1a; 在下面这个表 T 中&#xff0c;如果我执行 select * from T where k betwe…

022—pandas 根据时间段转换为各小时的秒数

前言 本例中&#xff0c;有一些时间段数据&#xff0c;需要将这些时间段里的时间以小时为分组&#xff0c;将24个小时段中每个小时所占用的秒数计算出来。 需求&#xff1a; 以第一条数据为例&#xff0c;它所在两个小时&#xff0c;7点段占用24分钟15秒&#xff0c;8点段54…
最新文章