题目
题解
发现题目给定的是个树结构，设$f_{i,j}$表示$i$在$i$的子树里排名为$j$的方案数，现在要合并$u$和$v$（$v$为$u$儿子）的答案，假设$v<u$，则有
$f_{u,i+j}=\sum_{i=1}^{siz_u}\sum_{j=1}^{siz_v}\sum_{k=1}^{j}f_{u,i}f_{v,k}{j+i-1\choose i-1}{siz_u-i+siz_v-j\choose siz_u-i}$
即表示原先$u$前面有$i$个，后面有$siz_u-i$个，因为子树互不影响，现在要把$j$个数插$u$前面，把$siz_v-j$个数插$u$后面
$v>u$也差不多，枚举的$k\in [j+1,siz_v]$即可
然后这个$f_{v,k}$是一段连续区间，所以直接用$f_{i,j}$表示答案的前缀和即可优化到$O(n^2)$
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int N=2e3+5,mod=1e9+7;
struct p{
int x,y;
}c[N<<1];
int T,n,num;
int h[N],siz[N];
int f[N][N],C[N][N],F[N];
char s[2];
bool a[N][N];
void add(int x,int y)
{
c[++num]=(p){h[x],y},h[x]=num;
c[++num]=(p){h[y],x},h[y]=num;
}
void dfs(int x=0,int fa=0)
{
siz[x]=1,f[x][1]=1;
for(int i=h[x],y;i;i=c[i].x)
if((y=c[i].y)^fa)
{
dfs(y,x);
for(int I=1;I<=siz[x];++I)
for(int J=0;J<=siz[y];++J)
if(a[x][y]) (F[I+J]+=1ll*C[I+J-1][I-1]*C[siz[x]+siz[y]-I-J][siz[x]-I]%mod*(f[x][I]-f[x][I-1]+mod)%mod*f[y][J]%mod)%=mod;
else (F[I+J]+=1ll*C[I+J-1][I-1]*C[siz[x]+siz[y]-I-J][siz[x]-I]%mod*(f[x][I]-f[x][I-1]+mod)%mod*(f[y][siz[y]]-f[y][J]+mod)%mod)%=mod;
siz[x]+=siz[y];
for(int I=1;I<=siz[x];++I)
f[x][I]=F[I],F[I]=0;
for(int I=1;I<=siz[x];++I)
f[x][I]=(f[x][I]+f[x][I-1])%mod;
}
}
void ss()
{
for(int i=0;i<=2e3;++i)
C[i][0]=C[i][i]=1;
for(int i=1;i<=2e3;++i)
for(int j=1;j<i;++j)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
int main()
{
scanf("%d",&T),ss();
while(T--)
{
scanf("%d",&n),num=0;
memset(h,0,sizeof(h));
memset(f,0,sizeof(f));
memset(a,0,sizeof(a));
for(int i=1,x,y;i<n;++i)
scanf("%d%s%d",&x,s,&y),add(x,y),a[x][y]=(s[0]=='<'?0:1),a[y][x]=!a[x][y];
dfs(),printf("%d\n",f[0][n]);
}
return 0;
}
