热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

HDU2196(Computer经典换根dp求一棵树中所有节点能达到的最长距离)

题目博主讲的很好:https:blog.csdn.netu013480600articledetails21831363#include#

题目
在这里插入图片描述博主讲的很好:https://blog.csdn.net/u013480600/article/details/21831363
在这里插入图片描述

#include
#define en '\n'
#define m(a,b) memset(a,b,sizeof a)
using namespace std;
typedef long long ll;
const int N=1e4+5;
struct Edge{int to;ll len;int nex;}edge[N<<1];
int head[N],tot;
inline void add(int from,int to,ll len){edge[&#43;&#43;tot]&#61;(Edge){to,len,head[from]};head[from]&#61;tot;edge[&#43;&#43;tot]&#61;(Edge){from,len,head[to]};head[to]&#61;tot;
}
ll dp[N][3];int son[N];//dp[x][0]:节点x正向最大距离 son[x]:节点x正向最大距离经过的儿子
void dfs1(int x,int fa){//dp[x][1]:节点不经过son[x]经过其他儿子的最大距离 dp[x][2]:节点x经过其父亲的反向最大距离dp[x][0]&#61;dp[x][1]&#61;dp[x][2]&#61;0;for(int i&#61;head[x];i;i&#61;edge[i].nex){int y&#61;edge[i].to;ll w&#61;edge[i].len;if(y&#61;&#61;fa) continue;dfs1(y,x);if(dp[x][0]<dp[y][0]&#43;w){//son[x]这个儿子要被换掉 所以次大距离也可被之前的son[x]的最大距离更新 因为son[x]马上不是之前的那个儿子了dp[x][1]&#61;max(dp[x][1],dp[x][0]);dp[x][0]&#61;dp[y][0]&#43;w,son[x]&#61;y;}else dp[x][1]&#61;max(dp[x][1],dp[y][0]&#43;w);//这个儿子不是正向最大距离经过的儿子 也可以用来看能否更新dp[x][1].}
}
void dfs2(int x,int fa){//dfs2函数是为了得到dp[x][2]for(int i&#61;head[x];i;i&#61;edge[i].nex){int y&#61;edge[i].to;ll w&#61;edge[i].len;if(y&#61;&#61;fa) continue;if(son[x]&#61;&#61;y) dp[y][2]&#61;max(dp[x][1],dp[x][2])&#43;w;//y节点是其父最大距离要经过的儿子else dp[y][2]&#61;max(dp[x][0],dp[x][2])&#43;w;//y节点不是其父最大距离要经过的儿子dfs2(y,x);}
}
int main(){int n;while(~scanf("%d",&n)){m(head,0),tot&#61;0;for(int i&#61;2;i<&#61;n;&#43;&#43;i){int y;ll w;scanf("%d%lld",&y,&w);add(i,y,w);}dfs1(1,1),dfs2(1,1);for(int i&#61;1;i<&#61;n;&#43;&#43;i) printf("%d\n",max(dp[i][0],dp[i][2]));}
}


推荐阅读
  • 本文探讨了Linux环境下线程私有数据(Thread-Specific Data, TSD)的概念及其重要性,介绍了如何通过TSD技术避免多线程间全局变量冲突的问题,并提供了具体的实现方法和示例代码。 ... [详细]
  • STM32代码编写STM32端不需要写关于连接MQTT服务器的代码,连接的工作交给ESP8266来做,STM32只需要通过串口接收和发送数据,间接的与服务器交互。串口三配置串口一已 ... [详细]
  • 题目概述:Sereja 拥有一个由 n 个整数组成的数组 a1, a2, ..., an。他计划执行 m 项操作,这些操作包括更新数组中的特定元素、增加数组中所有元素的值,以及查询数组中的特定元素。 ... [详细]
  • 题目描述:Balala Power! 时间限制:4000/2000 MS (Java/Other) 内存限制:131072/131072 K (Java/Other)。题目背景及问题描述详见正文。 ... [详细]
  • 本文针对HDU 1042 N! 问题提供详细的解析和代码实现。题目要求计算给定整数N(0 ≤ N ≤ 10000)的阶乘N!。文章不仅提供了算法思路,还附上了C++语言的具体实现。 ... [详细]
  • 本文详细介绍了 Node.js 中 OS 模块的 arch 方法,包括其功能、语法、参数以及返回值,并提供了具体的使用示例。 ... [详细]
  • 本文详细探讨了HihoCoder平台上的1398号问题——最大权闭合子图的求解方法。通过具体实例,深入分析了最大权闭合子图的概念及其算法实现。 ... [详细]
  • 网络流24题——试题库问题
    题目描述:假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取m道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算 ... [详细]
  • hlg_oj_1116_选美大赛这题是最长子序列,然后再求出路径就可以了。开始写的比较乱,用数组什么的,后来用了指针就好办了。现在把代码贴 ... [详细]
  • 本文介绍了一个来自AIZU ONLINE JUDGE平台的问题,即清洁机器人2.0。该问题来源于某次编程竞赛,涉及复杂的算法逻辑与实现技巧。 ... [详细]
  • 编码unicode解决了语言不通的问题.但是.unicode又有一个新问题.由于unicode是万国码.把所有国家的文字都编进去了.这就导致一个unicode占用的空间会很大.原来 ... [详细]
  • 探讨了一个包含纯虚函数的C++代码片段,分析了其中的语法错误及逻辑问题,并提出了修正方案。 ... [详细]
  • 本文详细介绍了在Luat OS中如何实现C与Lua的混合编程,包括在C环境中运行Lua脚本、封装可被Lua调用的C语言库,以及C与Lua之间的数据交互方法。 ... [详细]
  • 本文详细介绍如何在 Apache 中设置虚拟主机,包括基本配置和高级设置,帮助用户更好地理解和使用虚拟主机功能。 ... [详细]
  • 本文详细介绍了Linux系统中信号量的相关函数,包括sem_init、sem_wait、sem_post和sem_destroy,解释了它们的功能和使用方法,并提供了示例代码。 ... [详细]
author-avatar
搞笑宠物图片
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有