板刷 AtCoder ARC C！
[ARC171C] Swap on Tree
Problem
给定一棵 \(n\) 个节点的树，每个点有个权值 \(a_i\)，初始时 \(a_i=i\)。
你可以执行任意操作：选择一条边 \((u,v)\)，交换 \(a_u\) 和 \(a_v\)，并将这条边删掉。
问通过上述操作，最后 \((a_1,a_2,\cdots,a_n)\) 有多少种不同的排列方式，答案对 \(998244353\) 取模。
Tag
树形 dp。
Preface
2024.2.7 做的，大战了一上午。
Solution
树上计数，考虑树形 dp。
首先不妨设是根为 \(1\) 的有根树。一个子树内外来的数一定是从他的父亲来的，并且只能有至多一个，而实际上这个数是什么并不重要。所以考虑一个子树是否有外来的点作为状态。设 \(f_{u,0/1}\) 代表以 \(u\) 为根的子树与父亲有 / 没有交换分别的排列方式数。
对于和父亲没有交换的情况，考虑和 \(u\) 断了哪几条儿子的边，以什么顺序断的。那么有转移：
\[f_{u,0}=\sum_{S\subseteq son_u}|S|!\cdot\prod_{v\in S}dp_{v,1}\cdot\prod_{v\in son_u,v\notin S} \] 标签：AtCoder,子树,板刷,son,cdot,dp From： https://www.cnblogs.com/0x3b800001/p/18010932/AtCoder