AtCoder Beginner Contest 221 F Diameter set
洛谷传送门
AtCoder 传送门
显然，选出的每两个点都要组成一条直径。
还是显然，每条直径的重合部分只可能是一个点或一条边。简单证一下，没有重合显然不可能，重合超过一个点或一条边，直径会更长。
进一步发现，设直径点数为 \(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)\)。