本文从WordPress迁移而来, 查看全部WordPress迁移文章
树DP
【2013多校联合训练第一场】
题意:给出一棵无根树,边的距离都是1。对于查询m,意思是你要去到m个点,但是走过的距离最短,这里是允许走回头路,即一条路可以走多次,每走一次算1次距离
要距离最短,可以想到,不要走回头路就最好了。它又没规定起点和终点只是说走m个点,那就很宽松了。我们可以在树中找到最长链,这里定义最长链用点来定义,1->2->3,认为长度是3,经过的边是2,maxlink = 3
如果整个树的最长链 maxlink > m , 那么就可以在最长链上走,这样一定不会走完,也就不需要走回头路。走了m个点,走过的边就是m-1,所以距离就是m-1
如果对于整课树的最长链都少于m,那么就无可避免要揍回头路。首先我们从最长链的头走到尾,那么就走了maxlink个点,走了maxlink-1条边,还剩下m-maxlink个点要走,那么只好往回走,走到某点x,从这点出去走向另一个方向,再走m-maxlink个点就完成任务。但是可以从一个点x出去,走到底都走不够m-maxlink个点,那么又得走回头路,这个问题看起来就很复杂了,但是其实想想就知道,因为深度的关系,每次走下去又走回头路,都是走掉的距离的2倍。一开始走了maxlink个点,剩下m-maxlink个点,其实无论最后怎么走,回头路和新走出来的路都是m-maxlink(往深度那里想想或者画画图就出来了),答案为maxlink - 1 + 2*(m-maxlink)
找最长链用树DP,对于每个点记录最远距离和次元距离,注意这里的距离一定在不同分支,比较简单的树dp,算是本场比赛第2水的题了
1 |
|