P11766 题解

lmh_qwq · 2025-02-23 12:57:01 · 题解

找出树的直径的中点，可以证明从任意一个点出发的任意一条最长路径都经过这个中点，否则可以在树上找出一条比直径更长的路径。

把路径分成到中点之前和到中点之后两部分计算，需要记录一个节点子树的最大深度，最大深度的节点数量和子树大小。

容易做到 O(n)。细节参见代码。

哦不代码怎么出锅了。感谢 @FRZ_29 和 @dangbowen1008 的 hack 数据。等我找时间去改一下。