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 每条边应设置的边权。

一行一个整数 $n$，表示节点数。 接下来 $n-1$ 行，每行两个整数 $u,v$ 表示树上一条连接点 $u$ 和点 $v$ 的边。

输出共三行。 第一行一个整数，表示【小 L 得分的最大值】对 $998244353$ 取模的值。 第二行一个整数，表示小 L 应该选择的必经点 $t$，如有多种 $t$ 符合题意，请输出最小的 $t$。 第三行 $n-1$ 个整数，**按边的输入顺序**依次给出小 L 每条边应设置的边权。如有多种答案，请输出边权的字典序最小的答案。 注意：在小 L 得分最大的前提下，请首先最小化 $t$，其次最小化边权的字典序。 这里“边权的字典序”是指按边的输入顺序将边的边权看作一个排列，这个排列的字典序。

**本题采用捆绑测试。** 对于所有数据，$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)$。