当前位置: 首页 > 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; 方法…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...