树形dp
这道题是真滴SAO（骚）啊
首先，如果你按照拓扑排序的方法去做的话。。。。请重构代码吧。。。。
若不看方向，这些边显然会形成一棵树，那我们考虑树形dp。
因此，状态肯定有一维(dp[x])为当前节点为x。
显然，只开一维是不够的。那么，接下来，问题就来了，我们要如何设计第二维？
你会发现，当一个儿子转移到他父亲时，只用确定该儿子的当前位置就行了，于是(dp[x][i])表示在以x为根的子树拓扑序中x排第i个的方案数
接着，考虑转移。
对于一个节点x和它的一个儿子t，那么t要么在x前面，要么在x后面。
1.t在x前面。
来看一波图。
考虑一般情况，首先，(len[x]=size[x],len[t]=size[t])((size[x])表示以x为根的子树中点的数量)
那么对于(dp[x][i])和(dp[t][j])，假设合并后x排第k个
就有
[dp[x][k]=dp[x][k]+dp[x][i]cdot dp[t][j]cdot C_{k-1}^{i-1}cdot C_{size[x]+size[t]-k}^{size[x]-i}
]
2.t在x后面
同理，
[dp[x][k]=dp[x][k]+dp[x][i]cdot dp[t][j]cdot C_{k-1}^{i-1}cdot C_{size[x]+size[t]-k}^{size[x]-i}
]
于是，dp部分就有了如下代码:
void DFS(int x,int fa) {
size[x]=1;
dp[x][1]=1;
for(int i=head[x]; ~i; i=G[i].last) {
int t=G[i].ed,v=G[i].v;
if(t==fa)continue;
DFS(t,x);
for(int j=1; j<=size[x]+size[t]; j++)tmp[j]=0;
if(v==1) {
for(int j=1; j<=size[x]; j++) {
for(int k=1; k<=size[t]; k++) {
for(int o=j; o<=j+k-1; o++) {
tmp[o]+=dp[x][j]*dp[t][k]%MOD*C[o-1][j-1]%MOD*C[size[x]+size[t]-o][size[x]-j]%MOD;
tmp[o]%=MOD;
}
}
}
} else {
for(int j=1; j<=size[x]; j++) {
for(int k=1; k<=size[t]; k++) {
for(int o=j+k; o<=j+size[t]; o++) {
tmp[o]+=dp[x][j]*dp[t][k]%MOD*C[o-1][j-1]%MOD*C[size[x]+size[t]-o][size[x]-j]%MOD;
tmp[o]%=MOD;
}
}
}
}
for(int j=1; j<=size[x]+size[t]; j++)dp[x][j]=tmp[j];
size[x]+=size[t];
}
}
然而，算一下复杂度，你会发现，这是(O(n^3))的，显然这种写法会T。
于是我们要考虑优化。
首先，这种转移是累和的，那么我们想到可以用前缀和优化。
看一下转移方程：
[dp[x][k]=dp[x][k]+dp[x][i]cdot dp[t][j]cdot C_{k-1}^{i-1}cdot C_{size[x]+size[t]-k}^{size[x]-i}
]
你会发现，j只出现过1次，那么我们可以先枚举i和k第3维j直接前缀和搞一波。
整体代码:（注意i,j,k的范围）
#include<bits/stdc++.h>
#define int long long
#define MAXN 1010
const int MOD=1e9+7;
using namespace std;
int C[MAXN][MAXN],T,n,dp[MAXN][MAXN],head[MAXN],size[MAXN],ans,tot,tmp[MAXN],sum[MAXN];
struct node {
int ed,v,last;
} G[MAXN*10];
void Add(int st,int ed,int v) {
tot++;
G[tot]=node {ed,v,head[st]};
head[st]=tot;
}
void init() {//预处理组合数
C[0][0]=1;
for(int i=1; i<=MAXN-10; 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;
}
}
}
void DFS(int x,int fa) {
size[x]=1;
dp[x][1]=1;
for(int i=head[x]; ~i; i=G[i].last) {
int t=G[i].ed,v=G[i].v;
if(t==fa)continue;
DFS(t,x);
for(int j=1; j<=size[x]+size[t]; j++)tmp[j]=0;
for(int j=1; j<=size[t]; j++)sum[j]=0;
for(int j=1; j<=size[t]; j++)sum[j]=sum[j-1]+dp[t][j],sum[j]%=MOD;
if(v==1) {
for(int j=1; j<=size[x]; j++) {
for(int o=j; o<=j+size[t]-1; o++) {
tmp[o]+=dp[x][j]*((sum[size[t]]-sum[o-j]+MOD))%MOD*C[o-1][j-1]%MOD*C[size[x]+size[t]-o][size[x]-j]%MOD;
tmp[o]%=MOD;
}
}
} else {
for(int j=1; j<=size[x]; j++) {
for(int o=j+1; o<=j+size[t]; o++) {
tmp[o]+=dp[x][j]*((sum[o-j]-sum[0]+MOD))%MOD*C[o-1][j-1]%MOD*C[size[x]+size[t]-o][size[x]-j]%MOD;
tmp[o]%=MOD;
}
}
}
for(int j=1; j<=size[x]+size[t]; j++)dp[x][j]=tmp[j];
size[x]+=size[t];
}
}
signed main() {
init();
scanf("%lld",&T);
while(T--) {
ans=0;
memset(head,-1,sizeof(head));
memset(dp,0,sizeof(dp));
memset(size,0,sizeof(size));
tot=0;
scanf("%lld",&n);
int x,y;
char work[5];
for(int i=1; i<=n-1; i++) {
scanf("%lld",&x);
scanf("%s",work+1);
scanf("%lld",&y);
if(work[1]=='<') {
Add(x,y,1);
Add(y,x,0);
} else {
Add(x,y,0);
Add(y,x,1);
}
}
DFS(0,-1);
for(int i=1; i<=size[0]; i++)ans+=dp[0][i],ans%=MOD;
printf("%lld
",ans);
}
return 0;
}