首页/新闻资讯/正文详情

【题解-Acwing】1072. 树的最长路径

发布时间:2026/9/27 8:52:00 来源:云帆数科 栏目:资讯中心
【题解-Acwing】1072. 树的最长路径
题目1072. 树的最长路径题目描述给定一棵树树中包含 n 个结点编号1~n和 n−1 条无向边每条边都有一个权值。现在请你找到树中的一条最长路径。换句话说要找到一条路径使得路径两端的点的距离最远。注意路径中可以只包含一个点。输入格式第一行包含整数 n。接下来 n−1 行每行包含三个整数 ai,bi,ci表示点 ai 和 bi 之间存在一条权值为 ci 的边。输出格式输出一个整数表示树的最长路径的长度。数据范围1 ≤ n ≤ 10000 , 1 ≤ a i , b i ≤ n , − 10 5 ≤ c i ≤ 10 5 1≤n≤10000, 1≤a_i,b_i≤n, −10^5≤c_i≤10^51≤n≤10000,1≤ai​,bi​≤n,−105≤ci​≤105时空限制1s / 64MB输入样例6 5 1 6 1 4 5 6 3 9 2 6 8 6 1 7输出样例22思路由于存在负边权所以不能用两次 DFS / BFS的方法。可以用树形DP。核心思路是枚举中间节点u即从任意一个点u出发, 找到距离该点最远的2条路径, 加起来就是结果。为了找到最长路径和次长路径我们先来看看路径的分类。经过该点u的路径有以下三种类型① 以u的子树中的某个节点为起点以u为终点的路径② 以u的子树中的某个节点为起点以u的子树中的另一个节点为终点的路径③ 以u的子树中的某个节点为起点以u的祖先节点为终点的路径其中③又可以看作是u的祖先节点的情况①。所以我们只需要考虑情况①和②。代码如下#includebits/stdc.husingnamespacestd;constintN1000010;typedefpairint,intPII;intn,f[N][2],ans;vectorPIIg[N];voiddfs(intu,intfa){for(inti0;ig[u].size();i){PII tg[u][i];intvt.first,wt.second;if(vfa)continue;dfs(v,u);if(f[v][0]wf[u][0])f[u][1]f[u][0],f[u][0]f[v][0]w;elseif(f[v][0]wf[u][1])f[u][1]f[v][0]w;}ansmax(ans,f[u][0]f[u][1]);}intmain(){cinn;for(inti1;in;i){inta,b,c;cinabc;g[a].push_back({b,c}),g[b].push_back({a,c});}dfs(1,-1);coutans;return0;}结果如下100分参考https://www.acwing.com/solution/content/63883/感谢铅笔大佬的题解

相关推荐

XMind 用久了会遇到的 5 类问题,和我的进阶用法
XMind 用久了会遇到的 5 类问题,和我的进阶用法

写在前面 XMind 是我用得最久的效率工具之一,从读书笔记到项目拆解,几乎每天都在用。用得越久,越发现新手期根本意识不到的一些问题——不是软件坏了,是没摸清它的脾气。这篇把常见问题和几个进阶用法一起写出来,帮你… · 2026/9/27 8:51:54

MongoDB 高可用集群部署
MongoDB 高可用集群部署

MongoDB 高可用集群部署 一、方案概述 1.1 目标 在 K8s 高可用集群上,部署一套 MongoDB 高可用集群,具备: 高可用:3 数据节点副本集,容忍 1 个节点故障自动故障转移:主节点故障时,从节点自动… · 2026/9/27 8:51:48

2027 AI校园碳迹伙伴:构建数字化校园碳普惠生态的完整产品方案
2027 AI校园碳迹伙伴:构建数字化校园碳普惠生态的完整产品方案

引言 在“双碳”目标与绿色校园建设的双重驱动下,如何将抽象的“减碳”理念转化为师生可感知、可参与、可激励的具体行动,成为高校数字化建设的重要课题。本文将为你完整拆解一款名为 “AI校园碳迹伙伴” 的数字化校园碳普惠平台产品方案。 该平台旨在通… · 2026/9/27 8:51:35

isomorphic-git 的 deleteRemote 指南:从配置层面安全移除远端仓库
isomorphic-git 的 deleteRemote 指南:从配置层面安全移除远端仓库

开发工具 【免费下载链接】isomorphic-git A pure JavaScript implementation of git for node and browsers! 项目地址: https://gitcode.com/gh_mirrors/is/isomorphic-git 点击查看 免费下载 本篇文章围绕 isomorphic-git 公开 API 中的 deleteRemote 命令展开&… · 2026/9/27 9:28:56

做pc端网站行情揭秘:改需求拖一周?这份报价避坑指南必看
做pc端网站行情揭秘:改需求拖一周?这份报价避坑指南必看

做pc端网站行情揭秘:改需求拖一周?这份报价避坑指南必看 改个需求建站公司拖一周,这是多少老板心中的痛?我见过太多湖南中小企业的官网,刚上线时看着挺漂亮,结果后台改个Banner图、调个产品参数,沟通群里的消息发出去,对面已读不回,或者回复… · 2026/9/27 9:28:56

AngularFire 兼容版 Firestore 集合(Collection)完全指南:AngularFirestoreCollection 的流式 API 与实战用法
AngularFire 兼容版 Firestore 集合(Collection)完全指南:AngularFirestoreCollection 的流式 API 与实战用法

后端 【免费下载链接】angularfire Angular Firebase ❤️ 项目地址: https://gitcode.com/gh_mirrors/an/angularfire 点击查看 免费下载 本文以 docs/compat/firestore/collections.md 为骨架,结合仓库内 src/compat/firestore 的源码与测试&#x… · 2026/9/27 9:28:56

青岛OJ(QingdaoU/OnlineJudge)的开发与使用(3)——生成题目与导入用户
青岛OJ(QingdaoU/OnlineJudge)的开发与使用(3)——生成题目与导入用户

目录0.前言1.手动添加题目及测试样例2.导入导出题目3.用户生成与导入0.前言 前面的文章我们已经修改完前端并重新部署了,如果你没有看前面两篇,可以把我改好的docker-compose.yml文件里面的oj-backend的镜像部分直接替换掉,然后重新docker c… · 2026/9/27 9:28:50

minitab17下载、安装、修改中文环境
minitab17下载、安装、修改中文环境

目录0.minitab是什么1.下载2.安装3.设置中文环境0.minitab是什么 minitab是一款质量管理工具&#xff0c;导入数据后可以做统计分析。 1.下载 打开下面的网址&#xff0c;里面分别是安装程序的中文包。 (1) minitab17安装包 <1> 百度网盘 通过网盘分享的文件&#xf… · 2026/9/27 9:28:50

避坑指南:中企动力销售是做什么的及建站服务商怎么选
避坑指南:中企动力销售是做什么的及建站服务商怎么选

避坑指南:中企动力销售是做什么的及建站服务商怎么选 找建站公司怕被坑高价?别急,先搞清楚 中企动力销售是做什么的 。很多老板在预算里留了坑位,结果一接触销售,话术满天飞,最后账单比预期高出30%。今天不聊虚的,直接拆解这家头部服务商的业务逻… · 2026/9/27 9:28:44

MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现
MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现

简介&#xff1a;这套Matlab仿真工具完整呈现雷达信号脉冲压缩过程&#xff0c;从线性调频&#xff08;LFM&#xff09;信号生成、目标回波仿真到匹配滤波压缩处理均有可运行代码支撑&#xff0c;面向电子信息工程、计算机、数学等专业学生&#xff0c;适用于课程设计、期末大作… · 2026/9/27 0:00:01

汕头网站建设制作厂家避坑指南:5大注意事项救急
汕头网站建设制作厂家避坑指南:5大注意事项救急

汕头网站建设制作厂家避坑指南:5大注意事项救急 改个需求建站公司拖一周,这种憋屈事我见得太多了。 很多汕头老板找本地建站团队,签合同前看着方案挺美,一上线就变脸。 今天不聊虚的,直接拆解找 汕头网站建设制作厂家 时的5个核心 注意事项… · 2026/9/27 0:00:01

多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习
多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习

简介&#xff1a;基于PyTorch的多模态虚假新闻检测项目完整代码包&#xff0c;面向自然语言处理与计算机视觉交叉方向的开发者、科研人员及毕业设计选题者&#xff0c;解决社交媒体中文本与图像联合识别虚假新闻的问题。系统以BERT预训练模型提取文本语义特征&#xff0c;以Res… · 2026/9/27 0:00:01

MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现
MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现

简介&#xff1a;这套Matlab仿真工具完整呈现雷达信号脉冲压缩过程&#xff0c;从线性调频&#xff08;LFM&#xff09;信号生成、目标回波仿真到匹配滤波压缩处理均有可运行代码支撑&#xff0c;面向电子信息工程、计算机、数学等专业学生&#xff0c;适用于课程设计、期末大作… · 2026/9/27 0:00:01

汕头网站建设制作厂家避坑指南:5大注意事项救急
汕头网站建设制作厂家避坑指南:5大注意事项救急

汕头网站建设制作厂家避坑指南:5大注意事项救急 改个需求建站公司拖一周,这种憋屈事我见得太多了。 很多汕头老板找本地建站团队,签合同前看着方案挺美,一上线就变脸。 今天不聊虚的,直接拆解找 汕头网站建设制作厂家 时的5个核心 注意事项… · 2026/9/27 0:00:01

多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习
多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习

简介&#xff1a;基于PyTorch的多模态虚假新闻检测项目完整代码包&#xff0c;面向自然语言处理与计算机视觉交叉方向的开发者、科研人员及毕业设计选题者&#xff0c;解决社交媒体中文本与图像联合识别虚假新闻的问题。系统以BERT预训练模型提取文本语义特征&#xff0c;以Res… · 2026/9/27 0:00:01

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码