传送门
n 个关卡有 n-1 个限制
所以这些限制构成一颗树
考虑树形DP
对一颗子树单独考虑
考虑有多少种顺序
设 f [ i ] 表示节点 i 的子树的总方案数
考虑儿子节点如何与父节点合并
发现父子之间有限制条件，所以 f 多加一维 f [ i ] [ j ] 表示节点 i 在子树中排第 j 时的方案数
子树合并时就可以看成两个序列合并
比如像这样（x是v的父节点，x,v,是两颗子树的根）：
{ ，，x，， } + { 。。v 。。。} = { ，。。，v 。x ， 。。， }
上图就是 f [ x ] [ 3 ] 与 f [ v ] [ 3 ] 的一种合并方案 --> f [ x ] [ 7 ]
然后考虑方案数的增长
儿子的一部分合并到父节点左边，另一部分合并到父节点右边
对于父节点 x 和儿子节点 v
我们枚举合并后的父节点的排名 k ，枚举合并前的父节点排名 j，枚举儿子分离的中间点 o
儿子左半部分合并到父亲的方案有 C[ k-1 ] [ k-j ]
右部分合并父亲的方案有 C[ sz[x] - k ] [ sz[x]-sz[v]-j ]（sz[ x ]此时已经包括sz [ v ]）
然后可以得到完整的转移方程（不考虑父子关系的情况）:
$f_{xj}=\sum _{k=1}^{sz[x]}\sum_{j=1}^{min(sz[x]-sz[v],k)}\sum_{o=1}^{sz[v]}f_{xk}\times f_{vo}\times C_{k-1}^{k-j}\times C_{sz[x]-k}^{sz[x]-sz[v]-j}$
（sz是节点大小）
但这是O(n^3)的转移
优化十分显然，f [ v ] [ o ] 可以提出来用前缀和一起算，然后就是O(n^2)
然鹅我们还要考虑到父子间的限制...
那么如果 父节点要在子节点后 --> k-j ≥ o ≥ 1
反之 sz[v] ≥ o ＞ k-j
初始 f [ x ] [ 1 ] = 1 （合并前所有节点的子树只有它自己）
注意有多组数据，记得清空数组
实现看代码，要注意细节
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; typedef unsigned long long ll; inline int read() {int x=0; char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }return x; } const int N=2e3+7,mo=1e9+7; int fir[N],from[N<<1],to[N<<1],cnt; inline void add(int &a,int &b) {from[++cnt]=fir[a];fir[a]=cnt; to[cnt]=b; }inline ll fk(ll x) { return x>=mo ? x-mo : x; }//这样取模会快一点 int n; bool mp[N][N];//存父子间的大小关系 ll C[N][N];//组合数 void pre()//预处理组合数 {C[0][0]=1;for(int i=1;i<=n;i++)for(int j=0;j<=i;j++) C[i][j]=fk(C[i-1][j-1]+C[i-1][j]); } int sz[N]; ll f[N][N],g[N][N];//g是f的前缀和 void dfs(int x,int fa) {for(int i=fir[x];i;i=from[i]){int &v=to[i]; if(v==fa) continue;dfs(v,x); sz[x]+=sz[v];for(int j=sz[x];j;j--)//注意j从大到小转移，先更新大的再更新小的 {int L=min(sz[x]-sz[v],j); ll sum=0;for(int k=1;k<=L;k++){if(mp[x][v])//判断大小关系 {int l=j-k,r=sz[v];//o的范围if(l<r)//注意边界 {ll t=( C[j-1][j-k] * C[sz[x]-j][sz[x]-sz[v]-k] )%mo;sum=fk(sum+( (f[x][k]*t)%mo * fk(g[v][r]+mo-g[v][l]) )%mo);}}else{int r=min(j-k,sz[v]); ll t=( C[j-1][j-k] * C[sz[x]-j][sz[x]-sz[v]-k] )%mo;sum=fk(sum+( (f[x][k]*t)%mo * g[v][r] )%mo);}}f[x][j]=sum;}}for(int i=1;i<=sz[x];i++) g[x][i]=fk(g[x][i-1]+f[x][i]);//计算前缀和 } inline void clr() {for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=g[i][j]=mp[i][j]=0;for(int i=1;i<=n;i++) sz[i]=f[i][1]=1/*注意*/,fir[i]=0;cnt=0;//cnt别忘了清空 } int T; int main() {T=read();while(T--){int a,b; char c[5];n=read(); pre(); clr();for(int i=1;i<n;i++){a=read(); scanf("%s",c); b=read();a++; b++;add(a,b); add(b,a);if(c[0]=='<') mp[a][b]=1;else mp[b][a]=1;}dfs(1,1);ll ans=0;for(int i=1;i<=n;i++) ans=fk(ans+f[1][i]);printf("%lld\n",ans);}return 0; }