AT_arc167_f.[ARC167F] Tree Tree Tree

给定满足 $2\leq K\leq N$ 的整数 $N,K$。

问题 potato

有一棵有 $N$ 个顶点的有根带权树，顶点编号为 $1$ 到 $N$，顶点 $1$ 为根。

对于 $2\leq i\leq N$，顶点 $i$ 的父亲为 $p_i\;(1\leq p_i < i)$，且 $i$ 与 $p_i$ 之间的边的权值为 $q_{i-1}$。

其中，$q=(q_1,q_2,\dots,q_{N-1})$ 是 $(1,2,\dots,N-1)$ 的一个排列。

这里，定义 $cost(u,v)$ 为连接顶点 $u$ 和 $v$ 的简单路径上所有边的权值的最大值。

求 $\sum_{u=1}^{N}\ \sum_{v=u+1}^{N}\ cost(u,v)$。

---

问题 tomato

给定满足 $1\leq a<K$ 的整数 $a$。作为“问题 potato”的 $p,q$，满足 $p_K=a$ 的方案共有 $\frac{((N-1)!)^2}{K-1}$ 种。请计算所有这些方案下“问题 potato”的答案之和，并对 $998244353$ 取模。

对于 $a=1,\dots,K-1$，请分别求出“问题 tomato”的答案。

输入通过标准输入按以下格式给出。

$N$ $K$

输出 $K-1$ 行。第 $i$ 行输出当 $a=i$ 时“问题 tomato”的答案。

限制条件

• $2\leq K\leq N\leq 10^5$
• 输入均为整数。

由 ChatGPT 4.1 翻译