题目:
Keven现在有一棵树，现在Keven想知道在这颗树上任取两点，他们的距离的最大值是多少，Keven不会做这个题目，于是请教聪明的你，如果你帮助他解决这个问题，他将会让你的排名上升。
树中两点之间的距离定义为连接两点的路径边权之和。并且每条路径经过的次数不能超过1次。
输入格式:
第一行给出一个数字N，表示树的节点个数。（树的节点为1-N）
接下来N-1行，每行给出三个数字U，V，W，表示点U与点V之间有一条权值为W的路径。
（N<200000，W<100000000）
输出格式:
在一行中输出树上任意两点距离的最大值。
输入样例:
在这里给出一组输入。例如：
输出样例:
在这里给出相应的输出。例如：
案例解释:
第三个点到第四个点的距离最大，最大值为13。
思路:
我们首先看数据范围，
，那么我们只能采用
或
的做法
再看题意，给定一棵树，要求这棵树任意两个节点的最长距离，最能想到的就是暴力了，枚举每一个点作为起点，然后DFS或者BFS求从它出发能够达到的最大距离，再对所有的点能到达的最大距离取max，但这个算法的时间复杂度是
，因为有n个点，每个点计算它的最长距离是
的，那这个做法显然会超时
其实这道题是求树的直径的模板题，求解分为两种方法，一种通过两次遍历求解，一种一次遍历求解，复杂度都是
两次遍历：先从任意一点P出发，找离它最远的点Q，再从点Q出发，找离它最远的点W，W到Q的距离就是是的直径
证明如下：
①若P已经在直径上，根据树的直径的定义可知Q也在直径上且为直径的一个端点
②若P不在直径上，我们用反证法，假设此时WQ不是直径，AB是直径
—>若AB与PQ有交点C，由于P到Q最远，那么PC+CQ>PC+CA，所以CQ>CA，易得CQ+CB>CA+CB，即CQ+CB>AB，与AB是直径矛盾，不成立，如下图（其中AB，PQ不一定是直线，画成直线是为了方便）：
—>若AB与PQ没有交点，M为AB上任意一点，N为PQ上任意一点。首先还是NP+NQ>NQ+MN+MB，同时减掉NQ，得NP>MN+MB，易知NP+MN>MB，所以NP+MN+MA>MB+MA，即NP+MN+MA>AB，与AB是直径矛盾，所以这种情况也不成立，如下图：
两遍遍历代码:
一遍遍历：我们在数据结构中都求过二叉树的高度，通过递归左子树高度和右子树高度，最后取最大值就是树的高度，在这里我们同样可以借助这个思想，但是这里可不是二叉树了，而是n叉树，其中我们要求的最大距离就是，已该节点为根节点的最长子树高度加上次长子树高度，可以想象成是一个倒“V”字型，这种方法我们需要维护某一节点为根节点的子树高度最大值和次大值
一遍遍历代码:
来源：forget……
声明：本站部分文章及图片转载于互联网，内容版权归原作者所有，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！