算法提高之树的最长路径
算法提高之树的最长路径
-
核心思想:树形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;}
相关文章:
算法提高之树的最长路径
算法提高之树的最长路径 核心思想:树形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 命令中指定的分支名称中包含特殊字符或者语法错误时。需要确保指定的分支名称是正确的,并且没有任何不支持的字符。 例如,如果分支名称是 feature/branch,应该…...
机器学习第二天(监督学习,无监督学习,强化学习,混合学习)
1.是什么 基于数据寻找规律从而建立关系,进行升级,如果是以前的固定算式那就是符号学习了 2.基本框架 3.监督学习和无监督式学习: 监督学习:根据正确结果进行数据的训练; 在监督式学习中,训练数据包括输…...
Rust 解决循环引用
导航 循环引用一、现象二、解决 循环引用 循环引用出现的一个场景就是你指向我,我指向你,导致程序崩溃 解决方式可以通过弱指针,而Rust中的弱指针就是Weak 在Rc中,可以实现,对一个变量,持有多个不可变引…...
ICC2:如何解决pin density过高引起的绕线问题
我正在「拾陆楼」和朋友们讨论有趣的话题,你⼀起来吧? 拾陆楼知识星球入口 为了追求极致的利用率,综合往往会使用大量的AOI/OAI等多pin cell,然而后端实现过程中,工具为了解决绕线难题,又会通过降低local density的方法实现反向奔赴,即便如此,绕线后仍会残留不少问题,…...
Buuctf-Misc题目练习
打开后是一个gif动图,可以使用stegsolve工具进行逐帧看。 File Format:文件格式 Data Extract:数据提取 Steregram Solve:立体试图 可以左右控制偏移 Frame Browser:帧浏览器 Image Combiner:拼图,图片拼接 所以可以知道我们要选这个Frame Browser …...
费马小定理详解
费马小定理 定义: 设 p 为素数,a 为整数,则 a p ≡ a ( m o d p ) a^p \equiv a\ (\mod p) ap≡a (modp) ,若 p ∤ a p \nmid a p∤a ,则 a p − 1 ≡ 1 ( m o d p ) a^{p-1} \equiv 1\ (\mod p) ap−1≡1 (modp)…...
PXE批量安装
系统装机的三种引导方式 u盘光盘网络装机 光盘: 1.类似于usb模式 2.刻录模式 系统安装过程 加载boot loader Boot Loader 是在操作系统内核运行之前运行的一段小程序。通过这段小程序,我们可以初始化硬件设备、建立内存空间的映射图,从…...
stm32f103c8t6最小系统板
STM32F103C8T6最小系统板是为基于ARM Cortex-M3内核的STM32F103C8T6微控制器设计的电路板,它包含了单片机正常运行所需的最基本组件。以下是构成STM32F103C8T6最小系统板的基本部分: 单片机芯片:STM32F103C8T6本身,它是一款32位微…...
QCefView 在 Linux 下的编译(更新)
在前面的文章《QT 应用程序中集成浏览器》中已经介绍过 QCefView 的构建。这几天发现 QCefView 代码进行了更新,构建方式也发生了一点点变化,所以在此更新一下 QCefView 的编译方法。 QCefView 其实包含了两个项目,一个就是 QCefView 项目本身,另外一个就是 CefViewCore。…...
无卤素产品是什么?有什么作用?
无卤素产品,即在生产过程中完全不使用卤素元素——氟、氯、溴、碘等——的产品。 卤素元素,虽然在电子设备、材料等领域应用广泛,却也可能潜藏危害。其阻燃剂,一旦在产品生命周期结束后释放,将对土壤和水体造成污染&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…...
题目:线性代数
问题描述: 解题思路: 列相乘,然后行相加。 注意点:由于元素数据范围最大为1e6,两个元素相乘乘积最大为1e12,如果元素类型为int则在乘的过程中就会爆炸,所以需要开long long类型。 AC代码…...
docker学习笔记3:VmWare CentOS7安装与静态ip配置
文章目录 一、安装CentOS71、下载centos镜像2、安装二、设置静态ip三、xshell连接centos本专栏的docker环境是在centos7里安装,因此首先需要会安装centos虚拟机。 本篇博客介绍如何在vm虚拟机里安装centos7。 一、安装CentOS7 1、下载centos镜像 推荐清华源,下载如下版本 …...
leetcode 547.省份数量
思路:dfs 或者这道题用bfs也是可以的。 这道题有点迷惑性,这里的数组给的是无向图的数组,而并不是地图,这里需要着重注意一下。 而后,这里的状态数组st没必要是二维的,我们并不会去遍历所给的数组&#…...
Qt5 框架学习及应用 — 对象树
Qt 对象树 对象树概念Qt为什么使用对象树 ?将对象挂到对象树上 对象树概念 对象树:对于树的概念,相信许多学过数据结构的同学应该都不会陌生。在学习数据结构的时候我们所接触的什么二叉树、多叉树、哈夫曼树、AVL树、再到红黑树、B/B树………...
Ansible自动化运维工具---Playbook
一、playbook playbook是剧本的意思 通过 task 调用 ansible 的模块将多个 play 组织在一 个playbook中运行。 playbook本身由以下各部分组成: Tasks: 任务,即调用模块完成的某操作Variables: 变量Templates: 模板Handlers: 处理器,当某条…...
什么是接口和类?Java中的集合框架有哪些主要接口和类?
Java中的集合框架有哪些主要接口和类? Java中的集合框架(Java Collections Framework)提供了一套丰富的接口和类,用于存储和操作对象的集合。以下是Java集合框架中的主要接口和类: 主要接口 Collection: 这…...
算法学习笔记(最短路——Bellman-Ford)
B e l l m a n — F o r d Bellman—Ford Bellman—Ford是一种单源最短路径算法,可以用于边权为负的图,但是只能用于小图。 大概过程: 枚举每一条边,更新可以更新的节点(起点到自己距离为 0 0 0,从地点开…...
try-catch-finally的省略与springboot
在 Java 中,try-catch 块是用于捕获和处理异常的结构,它可以帮助您在代码中处理可能发生的异常情况。在某些情况下,您可能希望省略 try-catch 块并将异常向上抛出,让调用者处理异常。这种情况通常适用于以下情况: 方法…...
AFL++实战:从零开始用WSL搭建模糊测试环境(附libxml2案例)
AFL实战指南:WSL环境下的模糊测试从入门到精通 模糊测试(Fuzz Testing)作为软件安全测试的重要手段,近年来在漏洞挖掘领域展现出惊人的效果。对于Windows平台开发者而言,Windows Subsystem for Linux(WSL&…...
Vivado MIG IP核实战:DDR3控制器配置与仿真全流程解析
1. Vivado MIG IP核与DDR3控制器基础认知 第一次接触DDR3控制器时,我被那些密密麻麻的时序图吓得不轻。直到发现Xilinx的MIG(Memory Interface Generator)IP核,才明白原来FPGA开发可以这么"偷懒"。这个IP核就像个贴心的…...
从旅游Vlog到新闻视频:QVHIGHLIGHTS数据集在跨领域应用中的实战指南
QVHIGHLIGHTS数据集:跨领域视频内容智能解析的工程实践 当你在旅行Vlog中搜索"日落时分的海滩漫步",或在新闻视频中寻找"抗议活动现场冲突画面",传统视频平台只能返回整段视频——这就像给你一整本书而不是精确的页码。Q…...
Windows 10 64位系统下Neo4j社区版与桌面版安装全攻略(2023最新版)
1. Neo4j简介与安装准备 如果你正在寻找一款强大的图数据库来管理复杂的关系数据,Neo4j绝对是个不错的选择。作为目前最流行的开源图数据库,它用起来就像在画一张巨大的网络图——每个节点代表实体(比如人或产品),每条…...
Graphormer部署教程:/etc/supervisor/conf.d/graphormer.conf配置解析
Graphormer部署教程:/etc/supervisor/conf.d/graphormer.conf配置解析 1. 项目介绍 Graphormer是一种基于纯Transformer架构的图神经网络模型,专门为分子图(原子-键结构)的全局结构建模与属性预测而设计。该模型在OGB、PCQM4M等…...
仅限前500位开发者获取:20年MCP协议老兵手写《Python服务器模板源码认知地图》PDF+可执行调试镜像
第一章:MCP协议核心原理与Python服务器模板设计哲学MCP(Model Control Protocol)是一种轻量级、面向模型交互的双向通信协议,专为AI代理系统与外部工具服务之间的结构化指令交换而设计。其核心在于以JSON-RPC 2.0为传输语义基础&a…...
终极无损视频剪辑神器:LosslessCut完整指南与5大实用技巧
终极无损视频剪辑神器:LosslessCut完整指南与5大实用技巧 【免费下载链接】lossless-cut The swiss army knife of lossless video/audio editing 项目地址: https://gitcode.com/gh_mirrors/lo/lossless-cut 你是否曾因视频剪辑导致画质下降而烦恼ÿ…...
让你的调试日志五彩斑斓:J-Link RTT高级封装技巧(支持中文、浮点数、十六进制)
让你的调试日志五彩斑斓:J-Link RTT高级封装技巧(支持中文、浮点数、十六进制) 调试是嵌入式开发中不可或缺的一环,而高效的调试工具能显著提升开发效率。J-Link RTT(Real Time Transfer)作为一种无需额外硬…...
掌握罗技鼠标宏的5个技术维度:从原理到实战优化
掌握罗技鼠标宏的5个技术维度:从原理到实战优化 【免费下载链接】logitech-pubg PUBG no recoil script for Logitech gaming mouse / 绝地求生 罗技 鼠标宏 项目地址: https://gitcode.com/gh_mirrors/lo/logitech-pubg 一、技术原理解析:机械补…...
告别软件盗版烦恼:用YT88加密狗5分钟搞定C#/Java/Python源代码加密(附完整开发包下载)
5分钟实现多语言源代码加密:YT88加密狗实战指南 独立开发者最头疼的问题之一,就是辛苦编写的代码被轻易反编译或盗用。上周我的一个朋友就遇到了这种情况——他花了三个月开发的Python数据分析工具,刚上线两周就被破解并免费传播。这种经历在…...
