树形dp， dp[i][j] 表示以 i 为根的子树，i之前有 j 个数的方案数。转移的时候枚举u之前本来有 j 个数，v和子树中有 k 个数在u之前。以 v 必须放在u之前为例
dp[u][j+k]+=(j+kk)(size[u]+size[v]−1−j−ksize[v]−k)∗dp[u][j]∗∑x=0k−1dp[v][k] 注意一下更新的顺序，当然这也不是唯一写法。 有人说你这不是 O(n4) 的吗？首先最后一项 ∑ 可以用前缀和优化，其次考虑一次转移，代价是 O(size[u]∗size[v]) ，其中的 size[u] 是现有子树大小。把这个乘积展开，其实就是若干对点每对有一个 O(1) 的贡献。而每对点只在LCA处贡献一次，所以复杂度 O(n2) 。 #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); else for (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(); }