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
     
      #include
      
       #include
       
        #include
        
         #include
         
          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