题目链接
https://atcoder.jp/contests/arc171/tasks/arc171_c
题目大意
给定一颗 \(N\) 个节点的树，初始时编号为 \(i\) 的物品放在编号为 \(i\) 的节点上。
你可以进行以下操作任意多次（可以为 \(0\) 次）：
- 选择一条未被删除的边，假设这条边的两个端点编号分别为 \(u,v\)，交换节点 \(u, v\) 上的物品，并且将这条边删除。
设 \(a_i\) 为最终编号为 \(i\) 的节点上的物品编号，那么通过上述操作能形成多少种不同的序列 \((a_1, a_2, \dots, a_n)\)，答案对 \(998244353\) 取模。
数据范围
- \(1\le N \le 3\times 10^{3}\)
解题思路
首先，如果选择的边集不同，那么最终的结果序列一定不同；如果选择的边集相同，那么最终的结果序列有可能相同，也有可能不同。
先从最简单的菊花图的形状开始考虑，假设中间一个节点周围连接了 \(deg\) 个节点，容易发现，最终结果序列相同，当且仅当两种选法选边的顺序是一致的，总共能得到 \(deg!\) 种结果序列。
那如果是以 \(u\) 和 \(v\) 为中心的两个菊花中间用一条边连接起来呢？那么最终结果序列相同，当且仅当两种选法中 \(u\) 连接的边选择顺序相同，且 \(v\) 连接的边的选择顺序相同，总共能得到 \(deg_u! \times deg_{v}!\) 种结果序列。
由于一棵树就是一堆小的菊花图连接起来的，所以上面的结论可以推广到整棵树上。即最终结果序列 \((a_1, a_2, \dots, a_n)\) 相同，当且仅当两种选法分别对于树的每个节点 \(u\) 连接的边的选择顺序相同。
有了以上结论，假设最终选择的边集为 \(S\)，对于树上的每个节点 \(u\) 统计度数 \(deg_u\)，那么 \(S\) 对答案的贡献为 \(\displaystyle\prod_{i = 1}^{n} deg_i\)。
考虑树形 dp 统计贡献，设 \(f_{u, i}\) 代表以 \(u\) 为根的子树中，连接 \(u\) 与 \(u\) 的儿子的边总共选了 \(i\) 条，对答案的总贡献。设 \(g_{u, 0/1}\) 代表连接 \(u\) 和 \(u\) 的父亲的边是否选了对答案的总贡献。
枚举 \(u\) 的儿子 \(v\) 时，有转移 \(f_{u, i} \leftarrow f_{u, i - 1} \times g_{v, 1}\)，\(f_{u, i} \leftarrow f_{u, i} \times g_{v, 0}\)，\(g_{u, 0} = \sum f_{u, i} \times i!\)，\(g_{u, 1} = \sum f_{u, i} \times (i + 1)!\)。
最终答案为 \(g_{1, 0}\)（假设整棵树以节点 \(1\) 为根）。