Appearance
一棵树的直径指的是树中任意两个节点之间的最长路径长度。
树形DP,本质是枚举拐点
有时候DP计算边好写,有时候计算点好写,只需要记住边与点的转换关系即可(边+1=点,注意特殊情况点/边为0要特别处理)
ans=0 def f(root,fa): res=0 for son in g[root]: if son==fa: continue v=f(son,root)+1 global ans ans=max(ans,v+res) res=max(res,v) return res