题意

给出一个连成树的有向图，求拓扑序数量

数据范围：$1 \le n \le 1000$

题解

树形$dp$，用$f[i][j]$表示以$i$为根的子树中，节点$i$的排名为$j$的方案数
考虑转移，对于$u$为$v$的父节点，$x$在原序列中排名为$p_1$，新序列中排名为$p_3$；$y$在原序列中排名为$p_2$，新序列中排名为$p_4$，从$f[u][p_1]$与$f[v][p_2]$转移到$f[u][p_3]$，先考虑$p_3$的范围：

• 若$u$的拓扑序小于$v$，有$p_3 < p_4$，同时$p_1$左边的节点仍在$p_3$左边（$p_1 \le p_3$），$p_2$左边的节点有一部分可以在$p_3$左边（但必须留至少$1$个，因为题目要求子集必须相交），即$$p_1 \le p_3 \le p_1+p_2-1$$
• 若$u$的拓扑序大于$v$，有$p_3 > p_4$，同时$p_1,p_2$左边的节点都在$p_3$左边（$p_1+p_2 \le p_3$），但最多有$p_1+siz[v]$个点，即$$p_1+p_2 \le p_3 \le p_1+siz[v]$$

由于选择，还要乘组合数：

• $$C_{p_3-1}^{p_1-1}$$$p_3$左边的$p_3-1$个点中一定有$p_1-1$个来自$u$的原序列
• $$C_{siz[u]+siz[v]-p_3}^{siz[u]-p_1}$$$p_3$右边的$siz[u]+siz[v]-p_3$个点中一定有$siz[u]-p_1$个来自$u$的原序列

状态转移方程即为$$f[u][p_3]+ \!\! =\sum_{p_1}\sum_{p_2}\sum_{p_3} C_{p_3-1}^{p_1-1}C_{siz[u]+siz[v]-p_3}^{siz[u]-p_1}f[u][p_1]f[v][p_2]$$
但这样每次转移有$3$层循环，考虑优化
发现$p_2$在求和中只出现一次并且连续，可以用前缀和优化；先将$p_2$与$p_3$交换（注意更改限制条件）

$$ \begin{aligned} f[u][p_3]+ \!\! &=\sum_{p_1}\sum_{p_3}\sum_{p_2} C_{p_3-1}^{p_1-1}C_{siz[u]+siz[v]-p_3}^{siz[u]-p_1}f[u][p_1]f[v][p_2] \\ &= \sum_{p_1}\sum_{p_3} C_{p_3-1}^{p_1-1}C_{siz[u]+siz[v]-p_3}^{siz[u]-p_1}f[u][p_1]\sum_{p_2} f[v][p_2] \end{aligned} $$

这时可以直接把$dp$数组存为前缀和

注： 这样看似是$O(n^3)$的（外$dfs$遍历点$\times$内$2$层循环），但实际上内$2$层循环可以看作枚举点对$(p_1,p_3)$，而每对点最多枚举$1$次，因此总复杂度为$O(n^2)$

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1000+10;
const int mod=1e9+7;
int t,n,u,v;
char c;
struct edge{
    int nxt,to,w;
} e[N<<1];
int cnt;
int head[N],C[N][N],siz[N],dp[N][N],tmp[N];
inline void add(int u,int v,int w){
    e[++cnt]=edge{head[u],v,w};
    head[u]=cnt;
}
void dfs(int u){
    siz[u]=1;
    dp[u][1]=1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(siz[v])
            continue;
        dfs(v);
        memcpy(tmp,dp[u],sizeof(tmp));
        memset(dp[u],0,sizeof(dp[u]));
        if(e[i].w){
            for(int p1=1;p1<=siz[u];p1++)
                for(int p3=p1;p3<=p1+siz[v]-1;p3++)
                    (dp[u][p3]+=1ll*C[p3-1][p1-1]*C[siz[u]+siz[v]-p3][siz[u]-p1]%mod*tmp[p1]%mod*(dp[v][siz[v]]-dp[v][p3-p1])%mod)%=mod;
        }
        else{
            for(int p1=1;p1<=siz[u];p1++)
                for(int p3=p1+1;p3<=p1+siz[v];p3++)
                    (dp[u][p3]+=1ll*C[p3-1][p1-1]*C[siz[u]+siz[v]-p3][siz[u]-p1]%mod*tmp[p1]%mod*(dp[v][p3-p1])%mod)%=mod;
        }
        siz[u]+=siz[v];
    }
    for(int i=1;i<=siz[u];i++)
        (dp[u][i]+=dp[u][i-1])%=mod;
}
int main(){
    C[0][0]=1;
    for(int i=1;i<=1000;i++){
        C[i][0]=1;
        for(int j=1;j<=i;j++)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    }
    scanf("%d",&t);
    for(;t--;){
        cnt=0;
        memset(head,0,sizeof(head));
        memset(siz,0,sizeof(siz));
        scanf("%d",&n);
        for(int i=1;i<n;i++){
            scanf("%d %c %d",&u,&c,&v);
            u++,v++;
            add(u,v,c=='<');
            add(v,u,c=='>');
        }
        dfs(1);
        printf("%d\n",(dp[1][n]%mod+mod)%mod);
    }
    return 0;
}