【HEOI2013】bzoj3167 Sao

树形dp，$dp[i][j]$表示以$i$为根的子树，$i$之前有$j$个数的方案数。转移的时候枚举$u$之前本来有$j$个数，$v$和子树中有$k$个数在$u$之前。以$v$必须放在$u$之前为例

$$dp[u][j+k]+=\binom{j+k}{k}\binom{size[u]+size[v]-1-j-k}{size[v]-k}*dp[u][j]*\sum_{x=0}^{k-1}dp[v][k]$$
注意一下更新的顺序，当然这也不是唯一写法。
有人说你这不是 $O(n^4)$的吗？首先最后一项 $\sum$可以用前缀和优化，其次考虑一次转移，代价是 $O(size[u]*size[v])$，其中的 $size[u]$是现有子树大小。把这个乘积展开，其实就是若干对点每对有一个 $O(1)$的贡献。而每对点只在LCA处贡献一次，所以复杂度 $O(n^2)$。

#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
const int p=1000000007,maxn=1010;
int fir[maxn],ne[2*maxn],to[2*maxn],w[2*maxn],
dp[maxn][maxn],sum[maxn][maxn],size[maxn],
c[maxn][maxn],g[maxn],
n;
void add(int num,int u,int v,int x)
{ne[num]=fir[u];fir[u]=num;to[num]=v;w[num]=x;
}
void upd(int &x,int y)
{x=(x+y)%p;
}
void dfs(int u,int fa)
{int v;size[u]=dp[u][0]=1;for (int i=fir[u];i;i=ne[i])if ((v=to[i])!=fa){dfs(v,u);for (int j=0;j<size[u]+size[v];j++) g[j]=0;if (w[i]==1)for (int j=0;j<size[u];j++)for (int k=0;k<=size[v];k++)upd(g[size[u]+size[v]-1-j-k],(LL)c[j+k][j]*c[size[u]+size[v]-1-j-k][size[v]-k]%p*dp[u][size[u]-j-1]%p*(sum[v][size[v]-1]-sum[v][size[v]-k-1]+p)%p);elsefor (int j=0;j<size[u];j++)for (int k=0;k<=size[v];k++)upd(g[j+k],(LL)c[j+k][j]*c[size[u]+size[v]-1-j-k][size[v]-k]%p*dp[u][j]%p*sum[v][k-1]%p);size[u]+=size[v];for (int j=0;j<size[u];j++) dp[u][j]=g[j];}sum[u][0]=dp[u][0];for (int i=1;i<size[u];i++) sum[u][i]=(sum[u][i-1]+dp[u][i])%p;
}
void solve()
{int u,v;char s[3];scanf("%d",&n);for (int i=1;i<=n;i++) fir[i]=0;for (int i=1;i<n;i++){scanf("%d%s%d",&u,s,&v);u++,v++;if (s[0]=='<'){add(i*2,u,v,1);add(i*2+1,v,u,-1);}else{add(i*2,u,v,-1);add(i*2+1,v,u,1);}}dfs(1,-1);printf("%d\n",sum[1][n-1]);
}
int main()
{int T;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]+c[i-1][j-1])%p;scanf("%d",&T);while (T--) solve();
}