C++(clang++ 11.0.1) 解法, 执行用时: 86ms, 内存消耗: 16308K, 提交时间: 2022-09-30 15:58:53

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
const int mod = 1e9 + 7 , N = 2005 ;
int jc[N],inv[N] ;
int qsm(int a,int b)
{
	int ans=1 ;
	while(b)
	{
		if(b&1) ans=(ll)ans*a%mod ;
		a=(ll)a*a%mod ; b>>=1 ;
	}
	return ans ;
}
void init(int n=N-1)
{
	jc[0]=1 ;
	for(int i=1;i<=n;++i) jc[i]=(ll)jc[i-1]*i%mod ;
	inv[n]=qsm(jc[n],mod-2) ;
	for(int i=n;i>=1;--i) inv[i-1]=(ll)inv[i]*i%mod ;
}
int C(int n,int m)
{
	return (ll)jc[n]*inv[m]%mod*inv[n-m]%mod ;
}
int calc(int x,int y)
{
	return (ll)jc[x+y]*inv[x]%mod*inv[y]%mod ;
}
int n ;
vector<pair<int,int>> g[N] ;
int f[N][N],h[N],siz[N] ;
int sum(int x,int l,int r)
{
	return (f[x][r]-f[x][l-1]+mod)%mod ;
}
void dfs(int x,int fa)
{
	siz[x]=1 ; f[x][1]=1 ;
	for(auto &y:g[x])
	{
		int z=y.first ;
		if(z==fa) continue ;
		dfs(z,x) ;
		memcpy(h,f[x],sizeof(h)) ;
		memset(f[x],0,sizeof f[x]) ;
		if(y.second==1)
		{
			for(int i=1;i<=siz[x];++i)
				for(int j=i;j<siz[z]+i;j++)
					(f[x][j]+=(ll)C(j-1,i-1)*C(siz[x]+siz[z]-j,siz[x]-i)%mod*h[i]%mod*sum(z,j-i+1,siz[z])%mod)%=mod ;
		}
		else
		{
			for(int i=1;i<=siz[x];++i)
				for(int j=i+1;j<=siz[z]+i;j++)
					(f[x][j]+=(ll)C(j-1,i-1)*C(siz[x]+siz[z]-j,siz[x]-i)%mod*h[i]%mod*sum(z,1,j-i)%mod)%=mod ;
		}
		siz[x]+=siz[z] ;
	}
	for(int i=2;i<=siz[x];++i) (f[x][i]+=f[x][i-1])%=mod ;
}
void solve()
{
	scanf("%d",&n) ; char ch ;
	for(int i=1;i<=n;++i) g[i].clear() ;
	memset(f,0,sizeof(f)) ;
	memset(siz,0,sizeof(siz)) ;
	for(int i=1,x,y;i<n;++i)
	{
		scanf("%d %c %d",&x,&ch,&y) ; x++ ; y++ ; 
		g[x].push_back({y,ch=='<'}) ;
		g[y].push_back({x,ch=='>'}) ;
	}
	dfs(1,0) ;
	printf("%d\n",f[1][n]) ;
}
int main()
{
	init() ;
	int T ; scanf("%d",&T) ;
	while(T--) solve() ;
	return 0 ;
}