显然,选出的每两个点都要组成一条直径。
还是显然,每条直径的重合部分只可能是一个点或一条边。简单证一下,没有重合显然不可能,重合超过一个点或一条边,直径会更长。
进一步发现,设直径点数为 \(x\),如果 \(x \nmid 2\),重合部分是一个点,否则重合部分是一条边。
-
如果重合部分是点 \(u\),答案为 \(\prod\limits_{v, (u,v) \in E} (f_v + 1) - a - 1\),其中 \(f_v\) 为 \(u\) 为根时 \(v\) 的子树中有多少个点与 \(u\) 的距离为 \(\frac{x-1}{2}\),\(a\) 为整棵树中有多少个点与 \(u\) 的距离为 \(\frac{x-1}{2}\)。大概意思就是每个点可选可不选,最后减去 \(|S| \le 1\) 的 \(S\)。
-
如果重合部分是边 \((u,v)\),答案为 \(f_u \times g_v\),其中 \(f_u\) 为以 \(v\) 为根时 \(u\) 的子树中有多少个点到 \(u\) 距离为 \(\frac{x}{2} - 1\),\(g_v\) 为以 \(u\) 为根时 \(v\) 的子树中有多少个点到 \(v\) 距离为 \(\frac{x}{2} - 1\)。
时间复杂度 \(O(n)\)。
标签:Diameter,set,frac,个点,Beginner,AtCoder,重合,子树,根时 From: https://www.cnblogs.com/zltzlt-blog/p/17389478.html