正解:树形$dp$
解题报告:
考虑设$f_i$表示点$i$的子树内的拓扑序排列方案数有多少个.
发现这样不好合并儿子节点和父亲节点.于是加一维,设$f_{i,j}$表示点$i$的子树中点$i$在拓扑序中排名为$j$的拓扑序排列方案数有多少个$QwQ$
然后说下儿子节点$x$和父亲节点$y$的合并,就枚举下点$y$前面有多少个原属于$y$的点有多少个原属于$x$的点.
若要求是$x>y$,就$f_{y,k}=sum_{i=1}^{k} sum_{j=k-i+1}^{size_x} f_{y,i}cdot f_{x,j}cdot C(k-1,i-1)cdot C(size_u+size_v-k,size_u-i)$(昂这个$size$是当前的$size$鸭$QwQ$.
大概解释下,,,?就枚举原$y$的排名是$i$,原$x$的排名是$j$,目标状态$y$的排名是$k$.
然后$y$之前有$C(k-1,i-1)$的方案数,$y$之后有$C(size_u+size_v-k,size_u-i)$的方案数,总的就$f_{y,i}cdot f_{x,j}cdot C(k-1,i-1)cdot C(size_u+size_v-k,size_u-i)$.然后关于范围这个随便算下就星趴,,,?首先$i$是显然的?然后$j$有因为要求$x$在$y$后面所以就要$j-1geq k-i,jgeq k-i+1$,$over$
$x<y$差不多,不说了$QwQ$
然后发现复杂度不太可,考虑咋优化$QwQ$.
发现转移式中关于$j$只出现了一个$f_{x,j}$.所以直接前缀和优化掉就完事$QwQ.$
然后就欧克了,$over$
对了这题有道很相似的题改下就双倍经验辣,这儿$QwQ$