这道题建出模型之后就是一个树形图
首先我们不考虑有向边的关系
而是直接考虑树形\(dp\)
关键是怎么个树形\(dp\)
我们维护\(dp[u][i]\)表示当前\(u\)节点在已经遍历的子树中拓扑序排名为\(i\)的情况数
那么接下来就是经典的做法 合并\(u\)和子树\(v\)
我们假设当前\(u\)已经维护好的序列中排名为\(i\)
当前子树\(v\)已经维护好的序列中排名\(j\)
1.合并之后\(u\)排名比\(v\)靠前 为\(k\)
那么\(i≤k≤i+j-1\)
\[dp[u][k]+=C_{k-1}^{i-1}* C_{siz[u]+siz[v]-k}^{siz[u]-i}* dp[u][i]* dp[v][j]\]
2.合并之后\(u\)排名比\(v\)靠后 为\(k\)
那么\(j+i≤k≤i+siz[v]\)
\[dp[u][k]+=C_{k-1}^{i-1}C_{siz[v]+siz[u]-k}^{Isz[u]-i}* dp[u][i]* dp[v][j]\]
有上述我们可以发现 枚举\(i,j,k\)是\(O(n^3)\)的
所以我们需要优化
可以发现在上述\(dp\)式子中 只用一项涉及到了\(j\)
所以我们在确定了\(j\)以及\(k\)的范围之后
切换枚举顺序可以使用前缀和优化
\[1≤i≤siz[u]\]
\[i≤k≤i+siz[v]-1\]
\[∵i≤k≤i+j-1\]
\[∴j≥k-i+1\]
\[1≤i≤siz[u]\]
\[i+1≤k≤i+siz[v]\]
\[∵j+i≤k≤i+siz[v]\]
\[∴j≤k-i\]
所以我们可以使用前缀和优化
原文：https://www.cnblogs.com/LovToLZX/p/10625176.html