【tyvj1520】树的直径

2016年6月15日1,5552

描述 Description

树的直径,即这棵树中距离最远的两个结点的距离。每两个相邻的结点的距离为1,即父亲结点与儿子结点或儿子结点与父子结点之间的距离为1.有趣的是,从树的任意一个结点a出发,走到距离最远的结点b,再从结点b出发,能够走的最远距离,就是树的直径。树中相邻两个结点的距离为1。你的任务是:给定一棵树,求这棵树中距离最远的两个结点的距离。

输入格式 InputFormat

输入共n行
第一行是一个正整数n,表示这棵树的结点数
接下来的n-1行,每行三个正整数a,b,w。表示结点a和结点b之间有一条边,长度为w
数据保证一定是一棵树,不必判错。

输出格式 OutputFormat

输出共一行
第一行仅一个数,表示这棵树的最远距离

样例输入 SampleInput

样例输出 SampleOutput

数据范围和注释 Hint

10%的数据满足1<=n<=5
40%的数据满足1<=n<=100
100%的数据满足1<=n<=10000 1<=a,b<=n 1<=w<=10000

来源 Source

Tgotmacp

题解

此题求树上最长链,即树的直径,有很多方法
可以如题中所说,用两次bfs,求出1的最远点X,再求X的最远点Y,XY即为直径
这个证明比较容易,大致可以分三步
先证明1,X一定和直径有交
再证明X一定是直径的一个端点
那么找X的最远点Y,XY即为直径
或者可以采用dp做法,基于直径为某个点到其不同子树叶子的最长链+次长链
dp