树上任意两点都是连通的,相互可达的。
找树的直径:(树上最远的两个点之间的距离,相邻两个点之间距离为1)
1. 任取一点作为起点,找到距离该点最远的一个点 u。u 一定是某条直径的一个端点。DFS || BFS(BFS更优,防止爆栈)
2. 再找到距离 u 最远的一点 v。DFS || BFS(BFS更优,防止爆栈)
那么 u 和 v 之间的路径就是一条直径。
树形dp
原文:https://www.cnblogs.com/Maxx-el/p/14167441.html