首页 > 代码库 > HDU 2196 Computer （树形dp）
HDU 2196 Computer （树形dp）
题目链接
题意：就是给你一棵树，每条边都有一定的权值，然后让你找到每个点所能走到的最远距离
分析:
这个题还是有点晕，贴一下大神的分析，分析的很透彻
先以 1 作为根节点进行一次 dfs 遍历，遍历的时候把以 第 i 为根节点往子树方向可以走到的最远距离和次远距离给求出来，且这两个距离是不在同一个分支中的
然后我们进行第二次的从根节点开始dfs遍历，这时候我们要判断的是对于一个节点 i ，除了子树方向上可能有最远距离外，我通过父节点方向是否可以有更加远的距离
，而对于这个操作，我们只要访问父节点所能到达的最远距离，然后接上一段就行了，但是这里会产生一个问题——就是父节点的最远距离可能是会经过当前这个节点
的，因此我们要进行判断当前节点是否在父节点的最远距离的分支上
如果在的话，那么我们要换一个分支，且要是最远的，这个其实就是第一次dfs中求出的与最远路径不在同一分支上的次远路径，我们接上这段进行转移
如果不在的话，那么我们直接接上父节点的最远路径进行转移就行了
HDU 2196 Computer （树形dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。