【HDU2196】寻访

好吧我承认这道题不是hdu2196

不过这道题和那道差不多,可以类比233

题意:给你一棵无根树,从给定的几个点中选一个点出发,每次只能走一条边,求走遍树上所有点的最短距离。

首先可以发现,如果走完了还要回到起点,那么总距离就一定是两倍所有边的长度。不要求回来,则说明省掉了从某个点回到起点的距离。那么只要找这条最大的距离就可以了。于是这道题转化为求树的直径问题。DFS两遍即可。

不过有些点是不能作为起点的。所以还是有那么一些小不同:

第一遍DFS随便一个点,找出距它最远的点a0和最远的能作为起点的点a1;

第二遍DFS a0,找出距a0最远的能作为起点的点,记两点之间距离为l0

第三遍DFS a1,找出距a1最远的点,记两点之间距离为l1

则答案为2*所有边长-max(l0,l1)

说点什么

您将是第一位评论人!

提醒
wpDiscuz