算法提高之树的最长路径

2024-05-08 05:20

本文主要是介绍算法提高之树的最长路径,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

算法提高之树的最长路径

  • 核心思想:树形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;}
    

这篇关于算法提高之树的最长路径的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/969419

相关文章

VSCode设置python SDK路径的实现步骤

《VSCode设置pythonSDK路径的实现步骤》本文主要介绍了VSCode设置pythonSDK路径的实现步骤,包括命令面板切换、settings.json配置、环境变量及虚拟环境处理,具有一定... 目录一、通过命令面板快速切换(推荐方法)二、通过 settings.json 配置(项目级/全局)三、

使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)

《使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)》字体设计和矢量图形处理是编程中一个有趣且实用的领域,通过Python的matplotlib库,我们可以轻松将字体轮廓... 目录背景知识字体轮廓的表示实现步骤1. 安装依赖库2. 准备数据3. 解析路径指令4. 绘制图形关键

Java使用MethodHandle来替代反射,提高性能问题

《Java使用MethodHandle来替代反射,提高性能问题》:本文主要介绍Java使用MethodHandle来替代反射,提高性能问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录一、认识MethodHandle1、简介2、使用方式3、与反射的区别二、示例1、基本使用2、(重要)

如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)

《如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)》:本文主要介绍如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)问题,具有很好的参考价值,希望对大家有所帮助,如有... 目录先在你打算存放的地方建四个文件夹更改这四个路径就可以修改默认虚拟内存分页js文件的位置接下来从高级-

一文详解如何查看本地MySQL的安装路径

《一文详解如何查看本地MySQL的安装路径》本地安装MySQL对于初学者或者开发人员来说是一项基础技能,但在安装过程中可能会遇到各种问题,:本文主要介绍如何查看本地MySQL安装路径的相关资料,需... 目录1. 如何查看本地mysql的安装路径1.1. 方法1:通过查询本地服务1.2. 方法2:通过MyS

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

Python如何调用指定路径的模块

《Python如何调用指定路径的模块》要在Python中调用指定路径的模块,可以使用sys.path.append,importlib.util.spec_from_file_location和exe... 目录一、sys.path.append() 方法1. 方法简介2. 使用示例3. 注意事项二、imp

使用Python实现矢量路径的压缩、解压与可视化

《使用Python实现矢量路径的压缩、解压与可视化》在图形设计和Web开发中,矢量路径数据的高效存储与传输至关重要,本文将通过一个Python示例,展示如何将复杂的矢量路径命令序列压缩为JSON格式,... 目录引言核心功能概述1. 路径命令解析2. 路径数据压缩3. 路径数据解压4. 可视化代码实现详解1

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各