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

算法提高之树的最长路径

算法提高之树的最长路径

  • 核心思想:树形dp

    • 枚举路径的中间节点
    • 用f1[i] 表示i的子树到i的最长距离,f2[i]表示次长距离
    • 最终答案就是max(f1[i]+f2[i])
    • 在这里插入图片描述
  •   #include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 1e4+10,M = N<<1;int n;int h[N],e[M],ne[M],w[M],idx;int f1[N],f2[N],res;void add(int a,int b,int c){e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;}void dfs(int u,int father){f1[u] = f2[u] = 0;  //当前父节点没有更新过距离for(int i=h[u];~i;i=ne[i]){int j = e[i];if(j == father) continue;  //加边的时候双向边 不能往回走dfs(j,u);  //递归//新的值比最长还大 更新次长为原最长 最长为新最长if(f1[j] + w[i] >= f1[u]) f2[u] = f1[u] , f1[u] = f1[j] + w[i];//先判断上面 再判断下面 只比次长距离长 更新次长else if(f1[j] + w[i] > f2[u]) f2[u] = f1[j]+w[i];}res = max(res,f1[u]+f2[u]);}int main(){memset(h, -1, sizeof h);cin>>n;for(int i=0;i<n-1;i++){int a,b,c;cin>>a>>b>>c;add(a,b,c),add(b,a,c);}dfs(1,-1);  //随便一个点作根节点cout<<res<<endl;}
    

相关文章:

算法提高之树的最长路径

算法提高之树的最长路径 核心思想&#xff1a;树形dp 枚举路径的中间节点用f1[i] 表示i的子树到i的最长距离,f2[i]表示次长距离最终答案就是max(f1[i]f2[i]) #include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N …...

git/gerrit使用遇到的问题

Push时出现的多个问题及其解决 branch【...】not found 这个错误通常出现在 Git 命令中指定的分支名称中包含特殊字符或者语法错误时。需要确保指定的分支名称是正确的&#xff0c;并且没有任何不支持的字符。 例如&#xff0c;如果分支名称是 feature/branch&#xff0c;应该…...

机器学习第二天(监督学习,无监督学习,强化学习,混合学习)

1.是什么 基于数据寻找规律从而建立关系&#xff0c;进行升级&#xff0c;如果是以前的固定算式那就是符号学习了 2.基本框架 3.监督学习和无监督式学习&#xff1a; 监督学习&#xff1a;根据正确结果进行数据的训练&#xff1b; 在监督式学习中&#xff0c;训练数据包括输…...

Rust 解决循环引用

导航 循环引用一、现象二、解决 循环引用 循环引用出现的一个场景就是你指向我&#xff0c;我指向你&#xff0c;导致程序崩溃 解决方式可以通过弱指针&#xff0c;而Rust中的弱指针就是Weak 在Rc中&#xff0c;可以实现&#xff0c;对一个变量&#xff0c;持有多个不可变引…...

ICC2:如何解决pin density过高引起的绕线问题

我正在「拾陆楼」和朋友们讨论有趣的话题,你⼀起来吧? 拾陆楼知识星球入口 为了追求极致的利用率,综合往往会使用大量的AOI/OAI等多pin cell,然而后端实现过程中,工具为了解决绕线难题,又会通过降低local density的方法实现反向奔赴,即便如此,绕线后仍会残留不少问题,…...

Buuctf-Misc题目练习

打开后是一个gif动图&#xff0c;可以使用stegsolve工具进行逐帧看。 File Format:文件格式 Data Extract:数据提取 Steregram Solve:立体试图 可以左右控制偏移 Frame Browser:帧浏览器 Image Combiner:拼图&#xff0c;图片拼接 所以可以知道我们要选这个Frame Browser …...

费马小定理详解

费马小定理 定义&#xff1a; 设 p 为素数&#xff0c;a 为整数&#xff0c;则 a p ≡ a ( m o d p ) a^p \equiv a\ (\mod p) ap≡a (modp) &#xff0c;若 p ∤ a p \nmid a p∤a &#xff0c;则 a p − 1 ≡ 1 ( m o d p ) a^{p-1} \equiv 1\ (\mod p) ap−1≡1 (modp)…...

PXE批量安装

系统装机的三种引导方式 u盘光盘网络装机 光盘&#xff1a; 1.类似于usb模式 2.刻录模式 系统安装过程 加载boot loader Boot Loader 是在操作系统内核运行之前运行的一段小程序。通过这段小程序&#xff0c;我们可以初始化硬件设备、建立内存空间的映射图&#xff0c;从…...

stm32f103c8t6最小系统板

STM32F103C8T6最小系统板是为基于ARM Cortex-M3内核的STM32F103C8T6微控制器设计的电路板&#xff0c;它包含了单片机正常运行所需的最基本组件。以下是构成STM32F103C8T6最小系统板的基本部分&#xff1a; 单片机芯片&#xff1a;STM32F103C8T6本身&#xff0c;它是一款32位微…...

QCefView 在 Linux 下的编译(更新)

在前面的文章《QT 应用程序中集成浏览器》中已经介绍过 QCefView 的构建。这几天发现 QCefView 代码进行了更新,构建方式也发生了一点点变化,所以在此更新一下 QCefView 的编译方法。 QCefView 其实包含了两个项目,一个就是 QCefView 项目本身,另外一个就是 CefViewCore。…...

无卤素产品是什么?有什么作用?

无卤素产品&#xff0c;即在生产过程中完全不使用卤素元素——氟、氯、溴、碘等——的产品。 卤素元素&#xff0c;虽然在电子设备、材料等领域应用广泛&#xff0c;却也可能潜藏危害。其阻燃剂&#xff0c;一旦在产品生命周期结束后释放&#xff0c;将对土壤和水体造成污染&a…...

esp32-cam 1. 出厂固件编译与测试

0. 环境 - ubuntu18 - esp32-cam - usb转ttl ch340 硬件连接 esp32-camch340板子U0RTXDU0TRXDGNDGND5V5V 1. 安装依赖 sudo apt-get install vim sudo apt install git sudo apt-get install git wget flex bison gperf python python-pip python-setuptools python-serial p…...

题目:线性代数

问题描述&#xff1a; 解题思路&#xff1a; 列相乘&#xff0c;然后行相加。 注意点&#xff1a;由于元素数据范围最大为1e6&#xff0c;两个元素相乘乘积最大为1e12&#xff0c;如果元素类型为int则在乘的过程中就会爆炸&#xff0c;所以需要开long long类型。 AC代码…...

docker学习笔记3:VmWare CentOS7安装与静态ip配置

文章目录 一、安装CentOS71、下载centos镜像2、安装二、设置静态ip三、xshell连接centos本专栏的docker环境是在centos7里安装,因此首先需要会安装centos虚拟机。 本篇博客介绍如何在vm虚拟机里安装centos7。 一、安装CentOS7 1、下载centos镜像 推荐清华源,下载如下版本 …...

leetcode 547.省份数量

思路&#xff1a;dfs 或者这道题用bfs也是可以的。 这道题有点迷惑性&#xff0c;这里的数组给的是无向图的数组&#xff0c;而并不是地图&#xff0c;这里需要着重注意一下。 而后&#xff0c;这里的状态数组st没必要是二维的&#xff0c;我们并不会去遍历所给的数组&#…...

Qt5 框架学习及应用 — 对象树

Qt 对象树 对象树概念Qt为什么使用对象树 &#xff1f;将对象挂到对象树上 对象树概念 对象树&#xff1a;对于树的概念&#xff0c;相信许多学过数据结构的同学应该都不会陌生。在学习数据结构的时候我们所接触的什么二叉树、多叉树、哈夫曼树、AVL树、再到红黑树、B/B树………...

Ansible自动化运维工具---Playbook

一、playbook playbook是剧本的意思 通过 task 调用 ansible 的模块将多个 play 组织在一 个playbook中运行。 playbook本身由以下各部分组成&#xff1a; Tasks: 任务&#xff0c;即调用模块完成的某操作Variables: 变量Templates: 模板Handlers: 处理器&#xff0c;当某条…...

什么是接口和类?Java中的集合框架有哪些主要接口和类?

Java中的集合框架有哪些主要接口和类&#xff1f; Java中的集合框架&#xff08;Java Collections Framework&#xff09;提供了一套丰富的接口和类&#xff0c;用于存储和操作对象的集合。以下是Java集合框架中的主要接口和类&#xff1a; 主要接口 Collection&#xff1a; 这…...

算法学习笔记(最短路——Bellman-Ford)

B e l l m a n — F o r d Bellman—Ford Bellman—Ford是一种单源最短路径算法&#xff0c;可以用于边权为负的图&#xff0c;但是只能用于小图。 大概过程&#xff1a; 枚举每一条边&#xff0c;更新可以更新的节点&#xff08;起点到自己距离为 0 0 0&#xff0c;从地点开…...

try-catch-finally的省略与springboot

在 Java 中&#xff0c;try-catch 块是用于捕获和处理异常的结构&#xff0c;它可以帮助您在代码中处理可能发生的异常情况。在某些情况下&#xff0c;您可能希望省略 try-catch 块并将异常向上抛出&#xff0c;让调用者处理异常。这种情况通常适用于以下情况&#xff1a; 方法…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...