HDU 4607 Park Visit

树的直径就是最长路,求法其实很简单的,就是两遍dfs,第一遍dfs把终点的节点编号输出来,第二次用这个节点当成起点再来一遍,这回输出最高深度,就是直径。

这个直径用法就是,如果需要过的节点数少于直径长度,说明不用拐弯,沿着直径走就ok,如果需要过的节点数大于直径长度,说明要拐弯,拐弯进去还要再出来,相当于走了两遍,所以是直径长度加上二倍多出来的分支长度,调整一下就ok了。

Leave a Reply

Scroll to top