AT_hitachi2020_f Preserve Diameter

哦哦牛皮

给定一棵树，你需要加入一些边，使得它成为一个简单无向图，要求：

• 图的直径等于原树直径
• 加入任何一条新边都会让图的直径变小。

求方案数对 \(998244353\) 取模。

\(1\le n \le 2\times 10^5\)

考虑找到新图的一对距离最远的点，将其它点按照到它们的距离标号并分层。由于第二条要求的存在，显然连边方式是所有同层或层数差 \(1\) 的点对全部连边。这也可以推出新图中距离最远的点只有唯一一对。那么我们直接去算标号方案数，要求是树上相邻的点标号差最多为 \(1\)，且标号为 \(0\) 和直径长度 \(L\) 的点都唯一。那么我们得到了平方做法。

考虑直径中点，即树的中心。如果它是一个点，那么所有可能成为直径端点的点就是距离它为 \(\frac{L}{2}\) 的那些点，在这些点中选择两个所属子树不同的，从这两个点到中心的路径上点的标号当然是唯一的，其它点直接随意赋予标号，方案数为 \(3^{n-L-1}\)（考虑这个点和父亲的标号差是 \(-1/0/1\)）。这样做的问题是可能有好多点被标上了 \(0\) 和 \(L\)。所以我们将这个做法和上一部分的 DP 结合起来，具体地，现在我们不再关心这个点到底标了什么，但是记录：1. 这个子树内是否有标号为 \(0/L\) 的点；2. 这个子树内是否存在一个点一路向上跳到子树根都是 \(-1/1\)。这样直接树上 DP 就是 \(\Theta(n)\) 的。

如果树的中心是两个点（即连接这两个点的边的中点），那么我们只要在一侧选出 \(0\)，另一侧选出 \(L\)，两侧互不影响，还是采用上面的 DP 即可。