4607专题

hdu 4607 park visit 2013多校联合训练第一场

题目的大意是给你一棵树 ,相连节点之间的距离为一,让你找出一个路线访问到k个不同节点 (一条边在这个路径中可以被走多次),问你这样这个路径的距离最小值是多少?   转化之后其实就是要找出数的直径即任意2点间的最大距离,一种方法是任取一个节点做一次广搜找出其最长的子树,然后以该子树的最远的叶子上的节点作为起点再做一次广搜之后得到的最长子树的长度就是树的直径了 对于要访问的点的个数k 小于等于树