(这写了一个晚上QAQ,可能是我太蠢了吧.)

题目说只有\(n-1\)条边,然而每个点又相互联系.说明它的结构是一个类似树的结构,但是是有向边连接的,题目问的是方案个数,那么首先想到的肯定是树上dp.

但是这题有向边,从一个点出发,不一定可以遍历整棵树.那么肯定要对每条边建反边,打个标记分类讨论.

解决了建模的问题,接下来就是怎么dp了.

容易发现这个其实就是求这个"类树形图"的拓扑排序方案数,然而我们知道拓扑排序的方案计数是个NP问题,用状压解决,这题有"类树"这个优良特性.所以我们要另辟蹊径.

我们设状态的时候要保证这个状态尽量可以描述这个状态的特点,从而协助我们转移.考虑状态\(dp[u][i]\)表示u和它的子树的点组成的满足拓扑关系的排列的中u点在第i位上.这样以来,我们就根据这个状态知道了,u的位置,知道了u之前有多少个点,知道u之后有多少个点,我们还可以通过它和它子树的节点数推断要在一些范围插入一些点,是不是很棒~

考虑怎么转移呢?

首先是边界条件,一个点(没有子树)单独站在第一位的方案数是1.

再就是考虑合并子树信息.先讨论u优先于v的情况.

最开始,只有1个点,此时加入第一棵子树,这个时候\(dp[u][i]\)描述的状态到处都是空位,出了u站在i位置,其他的都随便这棵子树里的点乱站.我们考虑从\(dp[v][j]\)转移而来,于是就是u和v的位置固定了,其他的可以随意填充,其他的点有多少个呢?\(sz[v]\)吗?

等等好像还有一些限制! u要先于v! 那么v在合并后的排名必须在u之后,那么v在之前子树的排名最低最低也是\(k-i+1\)名,这样v就刚好在u后面一位.那么其他的\(k-1\)个点就随意分布u之前的\(i-1\)个空位之间,剩余的\(sz[u]-k\)个点在\(u\)之后的\(sz[u]-sz[v]-k\)个空位里,那么状态转移方程就是:

\[dp[u][i]=\sum_{k=1}^{min(i,sz[u]-sz[v]+1)}dp[u][k]*C_{sz[u]-sz[v]-k}^{sz[u]-k}*C_{i-1}^{k-1}\sum_{j=k-u+1}^{sz[v]}dp[v][j]\]

如果是v先于u再像上面那样分析就可以了.

#include
    
     #define maxn 1005#define mod 1000000007#define ll long longusing namespace std;int cnt,n,T,ans,sum[maxn][maxn];//dp[u][i]表示u节点和它的子树,组成的拓扑排列中,u的拓扑序int c[maxn][maxn],dp[maxn][maxn],sz[maxn],vis[maxn];int head[maxn],nxt[maxn<<1],w[maxn<<1],to[maxn<<1];int C(int n,int m){if(n<0||m<0||n
     
      =mod)x-=mod;}void add(int u,int v,int ww){    nxt[++cnt]=head[u];head[u]=cnt;    to[cnt]=v;w[cnt]=ww;}void init(){    for(int i=0;i<=1000;i++)c[i][0]=1;    for(int i=1;i<=1000;i++)        for(int j=1;j<=i;j++)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;}void clear(){    memset(dp,0,sizeof(dp));memset(sz,0,sizeof(sz));    memset(vis,0,sizeof(vis));memset(sum,0,sizeof(sum));    memset(head,0,sizeof(head));cnt=0;}void dfs(int u){    vis[u]=1;sz[u]=1;dp[u][1]=1;    for(int ii=head[u];ii;ii=nxt[ii])    {        int v=to[ii];if(vis[v])continue;        dfs(v);sz[u]+=sz[v];        if(w[ii])//u优先于v        {            for(int i=sz[u],s=0;i>=1;i--,dp[u][i+1]=s,s=0)//填表法合并子树信息,枚举u的拓扑序                for(int k=1;k<=min(sz[u]-sz[v],i);k++)//枚举u和其它已经合并到u上的子树的状态                {                    if(sz[v]<=i-k)continue;                    int tt=(sum[v][sz[v]]-sum[v][i-k]+mod)%mod;                    qm(s,(ll)dp[u][k]*tt%mod*C(i-1,k-1)%mod                       *C(sz[u]-i,sz[u]-sz[v]-k)%mod);                    /*                      暴力转移:                      for(int j=i-k+1;j<=sz[v];j++)                        qm(sum,(ll)dp[u][k]*dp[v][j]%mod                        *C(i-1,k-1)%mod*C(sz[u]-i,sz[u]-sz[v]-k)%mod);                     */                }        }        else//v优先于u        {            for(int i=sz[u],s=0;i>=1;i--,dp[u][i+1]=s,s=0)                for(int k=1;k<=min(sz[u]-sz[v],i-1);k++)                {                    int tt=sum[v][min(sz[v],i-k)];                    qm(s,(ll)dp[u][k]*tt%mod*C(i-1,k-1)%mod                       *C(sz[u]-i,sz[u]-sz[v]-k)%mod);                }        }    }    for(int i=1;i<=sz[u];i++)//前缀和优化        sum[u][i]=(sum[u][i-1]+dp[u][i])%mod;}int main(){    init();cin>>T;    while(T--)    {        char ty;clear();cin>>n;        for(int i=1,u,v;i
      
       >u>>ty>>v,v++,u++,add(u,v,ty=='<'),add(v,u,ty=='>');        dfs(1);ans=0;        for(int i=1;i<=n;i++)ans+=dp[1][i],ans%=mod;        printf("%d\n",ans);    }    return 0;}