hdu 2196 Computer (树的直径||树形dp)

hdu2196

题意:给出一棵树。。。求距离每个点的最远距离是多少。。。

思路:最远距离什么的。。能想到树的直径。。。但是有什么关系呢? 我们在求树的直径的时候。。。直径的两个端点是可以知道的。。。如果再从两个端点分别做两次bfs。。。每个点取两个距离的较大值就是答案。。。。?

1A.

 

 

20161201upd:更新一个dp的做法(虽然用树的直径搞貌似要更好想也更直观,不过为了体会dp的思想嘛。。。)

参考题解

 这道题要求的是从树上一点出发的最长路。考虑有根树,不难想到,从树上一点u出发的最长路必然是下述两种情况之一:
(1)第一步向下走,(一直向下,走到某叶子节点)
(2)第一步向上走。
考虑树形DP:
dp[0][u] : 从节点u向下走的最长路径
dp[1][u] : 从节点u向下走的次长路径
这里,次长路径的含义是:与某条选定的最长路径不重合的路径中最长的路径。
dp[2][u] : 从节点u第一步向上走所能获得的最长路径
注意:

考虑如何转移
对于节点u,考虑u的所有子节点v,用dp[0][v]来更新dp[0][u], dp[1][u]。
至于dp[2][u], 仍考虑两种情况:
(1)第二步向下走, 这样便转移到u的父亲节点f第一步向下走的情况。
这时还要考虑用dp[0][f]还是dp[1][f]来更新dp[2][u]:(kk:因为如果第一步向上走,然后又从父亲节点回到当前节点,那么这是无意义,并且等于没有更新向上走的情况,这也是要求次小的原因)如果从f第一步走到u能走出一条从f向下的最长路,就用dp[1][f]来更新dp[2][u],否则用dp[0][f]。
(2)第二步仍向上走,这样便转移到f第一步向上走的情况,即dp[2][f]。

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz