新闻详情

新闻详情

首页 / 资讯中心 / 详情

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

发布时间:2026/11/17 6:20:26来源:尧图网络
【题解-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/感谢铅笔大佬的题解
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

【外设】之大彩串口显示屏 2026/11/15 4:54:16

【外设】之大彩串口显示屏

大彩串口屏初步使用 1 .官网下载 STM32 屏幕 GUI 设计资料 http://www.gz-dc.com/category/typeid/4112 找到 STM32 Keil 工程,移植相关代码因项目而异进行移植,由于项目简单,本人只对用到的指令接口进行修改。 比如:注意事项&…

阅读更多 →
无法下载Windows系统iso文件 2026/11/17 5:42:44

无法下载Windows系统iso文件

当我遇到这个问题的时候,我打开了一个网站: 登录 然后我打算下载的时候: 突然那个官方的连接就可以下载了:

阅读更多 →
【清华代码熊】DeepSeek V4.1 Flash 后训练详解 2026/11/16 19:23:38

【清华代码熊】DeepSeek V4.1 Flash 后训练详解

📌 上期解析了 DeepSeek V4.1 Flash 模型架构改进,本期解析 DeepSeek V4.1 Flash 预训练/后训练技术: 🌟 预训练:45T 文本 多模态混合语料、直接训练 sparse attention(取消 DeepSeek V4 的 dense 冷启动&…

阅读更多 →
Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ... 2026/11/16 6:47:19

Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ...

文章主要内容和创新点 主要内容 本文聚焦于多模态大语言模型(MLLM)强化学习(RL)训练中的效率问题,提出了一个名为Shuffle-R1的框架。研究发现,当前RL训练存在两个关键缺陷: 优势值坍缩(Advantage Collapsing):批次中大多数优势值集中在零附近,导致有效梯度信号被淹…

阅读更多 →
PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction 2026/11/17 5:57:47

PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction

一、文章主要内容总结 本文聚焦于利用大型语言模型(LLMs)实现个人身份信息(PII)脱敏的研究,旨在解决传统脱敏方法(如基于规则的系统、领域特定命名实体识别(NER)模型)泛化能力差、跨格式/跨语境适应性弱的问题。 研究通过全面评估多种LLM架构(包括密集型LLM(D-LLM…

阅读更多 →
LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model 2026/11/16 17:28:18

LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model

文章主要内容和创新点 主要内容 本文聚焦于二进制图像-文本相关性评估任务(判断图像与文本“相关”或“不相关”),针对该任务中文本格式多样、相关性定义随场景变化等挑战,提出了基于多模态大语言模型(MLLM)的解决方案LLaVA-RE。 模型设计:LLaVA-RE基于LLaVA 1.5架构,…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉