题目描述
给你一棵树，让你判断树上每个节点是否在树的直径上。
-
树的直径：树上最远的两个点之间的距离。
-
树的直径可能不止一条。
具体思路
对于树的直径，我们有三种求法。
树形dp
设 \(d_x\) 表示 \(x\) 往下走能够到达最远距离，\(f_x\) 表示经过 \(x\) 的最长链的长度。
那么树的直径就是： $$\max_{1 \le x \le n} {f_x}$$
考虑如何求出 \(d_x\) 以及 \(f_x\)。
显然
\[d_x=\max_{y \in son(x)}{d_y+edge(x,y)}
\]
\[f_x=\max_{y,z \in son(x)}{d_y+edge(x,y)+d_z+edge(x,z)}
\]
我们如果每次枚举 \(x\) 的两个儿子 \(y\) 和 \(z\)，那么时间复杂度 \(O(n^2)\)。显然不是最优的