Description：

给出一棵由有向边构成的树，询问有多少种拓扑序。

$n\le 2000$

Solution：

记 $f[i][j]$ 表示 $i$ 号节点位于 $j$ 的方案数，若有边 $x\to y$ ， $x$ 是父亲，则说明 $x$ 在最后的拓扑序必须在 $y$ 前，枚举 $y$ 前有 $l$ 个点在 $x$ 前，则有转移： $f[x][j]+=f[x][j-l]\times f[y][k]\times C^{l}_{j-1}\times C^{siz[y]-l}_{siz[x]-j+siz[y]}$

若 $x$ 在最后的拓扑序在 $y$ 后，枚举 $y$ 后有 $l$ 个数在 $x$ 前，则有： $f[x][k+l+j]+=f[x][j]\times f[y][k]\times C^{j-1}_{j-1+k+l}\times C_{siz[y]-k-l+siz[x]-j}^{siz[x]-j}$

用 $l$ 代替 $k+l$ ： $f[x][l+j]+=f[x][j]\times f[y][k]\times C^{j-1}_{j-1+l}\times C_{siz[y]-l+siz[x]-j}^{siz[x]-j}$

用 $j$ 代替 $l+j$ 得： $f[x][j]+=f[x][j-l]\times f[y][k]\times C^{l}_{j-1}\times C_{siz[y]+siz[x]-j}^{siz[y]-l}$

发现其实是一样的，只是转移的区间不一样。

发现后面的组合数与 $k$ 无关，所以可以前缀和优化， $O(n^2)$

Code：

#include<algorithm> 

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

inline char getc()

{

	register char c = getchar();

	while(c != '<' && c != '>')c = getchar();

	return c;

}

#define MOD 1000000007

int n;

#define MAXN 1010

typedef unsigned long long ll;

ll f[MAXN][MAXN];

ll C[MAXN][MAXN];

inline void prework()

{

	C[0][0] = 1;

	for(int i = 1;i < MAXN;++i)

	{

		C[i][0] = 1;C[i][i] = 1;

		for(int j = 1;j < i;++j)

		{

			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;

		}

	}

	return;

}

struct edge

{

	int to,nxt;

	bool tag;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;e[edgenum].tag = true;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;e[edgenum].tag = false;

	return;

}

bool vis[MAXN];

int siz[MAXN];

int g[MAXN];

void dp(int k)

{

	f[k][1] = 1;

	vis[k] = true;

	siz[k] = 1;

	for(register int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		dp(e[i].to);

		siz[k] += siz[e[i].to];

		for(register int j = 1;j <= siz[k];++j)

		{

			g[j] = 0;

			if(e[i].tag)

			{

				for(register int l = 0;l < j && l < siz[e[i].to];++l)

				{

					g[j] = (g[j] + f[k][j - l] * (f[e[i].to][siz[e[i].to]] - f[e[i].to][l] + MOD) % MOD * C[j - 1][l] % MOD * C[siz[k] - j][siz[e[i].to] - l] % MOD) % MOD;

				}

			}

			else

			{

				for(register int l = 1;l < j && l <= siz[e[i].to];++l)

				{

					g[j] = (g[j] + f[k][j - l] * f[e[i].to][l] % MOD * C[j - 1][l] % MOD * C[siz[k] - j][siz[e[i].to] - l] % MOD) % MOD;

				}

			}

		}

		for(register int j = 1;j <= siz[k];++j)

		{

			f[k][j] = g[j];

			g[j] = 0;

		}

	}

	/*cout << k << endl;*/

	for(register int i = 1;i <= siz[k];++i)f[k][i] = (f[k][i] + f[k][i - 1]) % MOD;

	return;

}

void work()

{

	scanf("%d",&n);

	memset(lin,0,sizeof(lin));

	edgenum = 0;

	memset(vis,false,sizeof(vis));

	int a,b;

	char c;

	for(int i = 1;i < n;++i)

	{

		a = read();c = getc();b = read();

		++a;++b;

		if(c == '>')add(a,b);

		else add(b,a);

	}//cout << "k e[i].to l : siz[k] j - siz[e[i].to] d - f[k][j - l] f[e[i].to][d] C[j - 1][l] C[siz[k] - j][siz[k] - l]" << endl; 

	memset(f,0,sizeof(f));

	dp(1);

	cout << f[1][n] << endl;

	return;

}

int main()

{

	prework();

	int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}