这个依赖关系是个树,可以考虑树型dp,设f_i表示子树i的答案
因为这是个序列问题,是要考虑某个数的位置的,所以设\(f_{i,j}\)表示子树i构成的序列,i在第j个位置的方案.转移依次合并儿子\(y\),每次枚举一个位置j,以及枚举儿子\(y\)的序列中有k个数放在插前面,可以得到\(f_{x,j+k}\leftarrow f_{x,j}*w*\binom{j-1+k}{k}*\binom{sz_x+sz_y-j-k}{sz_y-k}\),组合数即考虑插入的方式
还有一个w不知道,如果要求\(x\)在\(y\)前面,那么\(y\)要在自己子树序列的\(k+1\)位置及以后所以\(w=\sum_{i=k+1}^{sz_y} f_{y,i}\),否则要在\(k\)及以前,所以\(w=\sum_{i=1}^{k} f_{y,i}\),显然可以记前缀和
最后答案为根的dp值总和.注意到合并复杂度,这些合并等价于每个点对都在lca处贡献一个\(O(1)\),所以总复杂度为\(O(n^2)\)
#include<bits/stdc++.h>
#define LL long long
#define db double
#define il inline
#define re register
using namespace std;
const int N=1000+10,mod=1e9+7;
il int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int to[N<<1],nt[N<<1],w[N<<1],hd[N],tot=1;
il void add(int x,int y,int z)
{
++tot,to[tot]=y,nt[tot]=hd[x],w[tot]=z,hd[x]=tot;
++tot,to[tot]=x,nt[tot]=hd[y],w[tot]=z^1,hd[y]=tot;
}
int c[N][N],f[N][N],g[N],sz[N],pr[N][N],sf[N][N];
void dp(int x,int ffa)
{
sz[x]=1;
f[x][1]=1;
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
if(y==ffa) continue;
dp(y,x),sz[x]+=sz[y];
memset(g,0,sizeof(g));
if(w[i]==0)
{
for(int j=sz[x]-sz[y];j;--j)
for(int k=0;k<=sz[y];++k)
g[j+k]=(g[j+k]+1ll*f[x][j]*c[j-1+k][k]%mod*c[sz[x]-j-k][sz[y]-k]%mod*sf[y][k+1]%mod)%mod;
}
else
{
for(int j=sz[x]-sz[y];j;--j)
for(int k=0;k<=sz[y];++k)
g[j+k]=(g[j+k]+1ll*f[x][j]*c[j-1+k][k]%mod*c[sz[x]-j-k][sz[y]-k]%mod*pr[y][k]%mod)%mod;
}
memcpy(f[x],g,sizeof(g));
}
for(int i=1;i<=sz[x];++i) pr[x][i]=(pr[x][i-1]+f[x][i])%mod;
sf[x][sz[x]+1]=0;
for(int i=sz[x];i;--i) sf[x][i]=(sf[x][i+1]+f[x][i])%mod;
}
int main()
{
for(int i=0;i<=1000;++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;
}
int T=rd();
while(T--)
{
memset(f,0,sizeof(f));
memset(hd,0,sizeof(hd)),tot=1;
int n=rd();
for(int i=1;i<n;++i)
{
int x=rd()+1,z=(getchar())=='>',y=rd()+1;
add(x,y,z);
}
dp(1,0);
int ans=0;
for(int i=1;i<=n;++i) ans=(ans+f[1][i])%mod;
printf("%d\n",ans);
}
return 0;
}