不好讲，直接上式子吧=。=
设$dp[i][j]$表示考虑完$i$的子树后$i$的排名为$j$的方案数，然后转移类似树形背包，具体来说是(这里假设子树在$i$后选，其实反过来还用这个式子答案也是一样的，因为全反了)
$ans+=dp[nde][k]*dp[g][min(j-k,siz[g])]*C_{j-1}^{k-1}*C_{siz[nde]+siz[g]-j}^{siz[nde]-k}$
其中$j$是枚举的当前点加入$i$这个子树之后$i$前面总共有几个数，$k$是枚举的当前点加入这个子树之后$i$前面还有几个原来是$i$的，$g$是子树，解释一下
前两个是已有的信息，不解释了，$C_{j-1}^{k-1}$表示$i$已经有的这$k$个点随便排(原有顺序还要保持不变，所以是C)，后面那个$C_{siz[nde]+siz[g]-j}^{siz[nde]-k}$同理
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=1005,mod=1e9+7; 6 int fac[N],inv[N],siz[N],f[N][N]; 7 int p[N],noww[2*N],goal[2*N],val[2*N]; 8 int T,n,t1,t2,cnt; char rd[5]; 9 void Link(int f,int t,int v) 10 { 11 noww[++cnt]=p[f],p[f]=cnt; 12 goal[cnt]=t,val[cnt]=v; 13 } 14 int Qpow(int x,int k) 15 { 16 if(k==1) return x; 17 int tmp=Qpow(x,k/2); 18 return k%2?1ll*tmp*tmp%mod*x%mod:1ll*tmp*tmp%mod; 19 } 20 int C(int a,int b) 21 { 22 if(a<b) return 0; 23 return 1ll*fac[a]*inv[b]%mod*inv[a-b]%mod; 24 } 25 void Prework() 26 { 27 fac[0]=inv[0]=1; 28 for(int i=1;i<=1000;i++) 29 fac[i]=1ll*fac[i-1]*i%mod; 30 inv[1000]=Qpow(fac[1000],mod-2); 31 for(int i=999;i;i--) 32 inv[i]=1ll*inv[i+1]*(i+1)%mod; 33 scanf("%d",&T); 34 } 35 void Init() 36 { 37 memset(p,0,sizeof p); 38 memset(f,0,sizeof f); 39 cnt=0,scanf("%d",&n); 40 for(int i=1;i<n;i++) 41 { 42 scanf("%d%s%d",&t1,rd,&t2),t1++,t2++; 43 Link(t1,t2,rd[0]=='<'),Link(t2,t1,rd[0]=='>'); 44 } 45 for(int i=1;i<=n;i++) f[i][1]=1; 46 } 47 void DFS(int nde,int fth) 48 { 49 siz[nde]=1; 50 for(int i=p[nde];i;i=noww[i]) 51 { 52 int g=goal[i]; 53 if(g!=fth) 54 { 55 DFS(g,nde); 56 if(val[i]) 57 { 58 for(int j=siz[nde]+siz[g];j;j--) 59 { 60 int tmp=0; 61 for(int k=1;k<=min(j,siz[nde]);k++) 62 if(j-k+1<=siz[g]) 63 tmp+=1ll*f[nde][k]*(f[g][siz[g]]-f[g][j-k]+mod)%mod*C(j-1,k-1)%mod*C(siz[nde]+siz[g]-j,siz[nde]-k)%mod,tmp%=mod; 64 f[nde][j]=tmp; 65 } 66 } 67 else 68 { 69 for(int j=siz[nde]+siz[g];j;j--) 70 { 71 int tmp=0; 72 for(int k=1;k<=min(j,siz[nde]);k++) 73 if(min(j-k,siz[g])>=1) 74 tmp+=1ll*f[nde][k]*f[g][min(j-k,siz[g])]%mod*C(j-1,k-1)%mod*C(siz[nde]+siz[g]-j,siz[nde]-k)%mod,tmp%=mod; 75 f[nde][j]=tmp; 76 } 77 } 78 siz[nde]+=siz[g]; 79 } 80 } 81 for(int i=1;i<=siz[nde];i++) 82 f[nde][i]=(f[nde][i]+f[nde][i-1])%mod; 83 } 84 int main() 85 { 86 Prework(); 87 while(T--) 88 Init(),DFS(1,0),printf("%d ",f[1][n]); 89 return 0; 90 }