P11627 [迷宫寻路 Round 3] 游戏

小 L 正在玩游戏，游戏地图是一颗 $n$ 个节点的树，定义一条树上路径的长度为路径上所有边的边权之和，路径可以重复经过点和边。特别的，若路径不包含任何边，则其长度为 $0$。 小 L 会选择一个点作为必经点 $t$，接着，小 L 会设置每条边的边权，使得边的边权构成一个 $1$ 到 $n-1$ 的**排列**。 定义：小 L 的得分为 $\sum_{1 \leq u,v \leq n} \operatorname{dist}(u,v)$，其中 $\operatorname{dist}(u,v)$ 为在经过必经点 $t$ 的前提下，长度**最小的**从 $u$ 到 $v$ 的路径的长度。 小 L 希望最大化自己的得分，请你解答以下问题： 第一问：求他得分的**最大值**对 $998244353$ 取模的值。 第二问：求若要最大化他的得分，小 L 应该选择的必经点 $t$ 和小 L 每条边应设置的边权。

无

无

**本题采用捆绑测试。** 对于所有数据，$1\le n\le 10^5$。 | 子任务编号 | $n\leq$ | 特殊性质 1 | 特殊性质 2 | 分数 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $0$ | $50$ | 否 | 否 | $10$ | | $1$ | $1000$ | 否 | 否 | $20$ | | $2$ | $10^5$ | 是 | 否 | $10$ | | $3$ | $10^5$ | 否 | 是 | $10$ | | $4$ | $10^5$ | 否 | 否 | $50$ | 特殊性质 1：存在一个对点重标号的方案，使得第 $i$ 条边为 $(1,i+1)$。 特殊性质 2：存在一个对点重标号的方案，使得第 $i$ 条边为 $(i,i+1)$。