# [题解] 2023 杭电多校 Many Topological Problems [树计数]

# 题目大意

# Topological Problem

给定一个$n$ 个节点的有标号有根树和整数$k$，称一个长度为 n 的排列$a$ 为好的，当且仅当$\forall i,1\le i\le n$, 满足$a_{fa[i]} \lt a_i \le a_{fa[i]}+k$,$fa[i]$ 表示$i$ 的父节点。

# Many Topological Problems

给定$n,k$, 对于每一形态的$n$ 节点有标号有根树，计算给定$k$ 时的 Topological Problem 答案并求和。

# 题解

一开始看到树的计数就开始想 pruffer 序列，然后就绕道沟里出不来了哎。还是见识太少脑袋太木

实际上这个题参考题目的提示：拓扑。树的拓扑可以看作从根节点开始搜索，从父亲到儿子的过程。
考虑一般随机化构造一棵树的过程，从放入根节点$1$ 开始，之后的每个节点$i$ 选择父节点，范围都在$[1,i-1]$，这样能造出$\prod\limits_{i=2}^{n} (i-1)=(n-1)!$ 种形态的树，这恰好也是$k=n$ 时问题的答案。
这题$k$ 限制的是节点$i$ 的父节点选取范围，变成了$[i-k+1,i-1]$，那么这时可以构造$ans=\prod\limits_{i=2}^{k}(i-1)\prod\limits_{i=k+1}^{n} k=(k-1)!k^{n-k}$ 种。
回到好的排列上来，我们考虑对于任意一个排列，对应多少种树使得这个排列是好的。实际上，对于任意一个排列，都有$ans$ 种树使得排列是好的。
为什么呢？由于限制 (每个点的权值都比父节点大)，我们按权值从小到大的顺序计数，等效于按照从父亲到儿子的顺序计数。将点权排序之后，所有排列的情况化为同一个问题，这个结果只与$n$ 有关，与节点上的权值无关。
即答案为$n!(k-1)!k^{n-k}$。