题解 P4099 【[HEOI2013]SAO 】
devout
2020-11-10 19:57:23
> Welcome to SAO ( Strange and Abnormal Online)
**description**
给你一棵有向树，问这棵树的拓扑序的情况数。
**solution**
考虑树形dp，我们用 $f[u][i]$ 表示以 $u$ 为根的子树中，$u$ 的拓扑序排名为 $i$ 的方案数
考虑 $u$ 的新的一个子节点时，对于边的方向分类讨论，假设 $u$ 要在 $v$ 之后。
那么可以推出转移：
$$f[u][i+k]=\sum_{j\leq k} f[u][i]\times f[v][j]\times\binom{i+k-1}{i-1}\times\binom{siz_u+siz_v-i-k}{siz_u-i}$$
解释一下，$f[u][i+k]$ 要从 $f[u][i]$ 和 $f[v][j]$ 转移过来的话，那么以 $v$ 为根的子树中应该有 $k$ 个点拓扑序在 $u$ 之前，合并之后在 $u$ 前面有 $i-k-1$ 个位置，任意从中选出 $i-1$ 个放 $f[u][i]$ 中在 $i$ 之前的，剩下的放在 $v$ 子树中的，就是 $\binom{i+k-1}{i-1}$，相应的，放在 $u$ 之后的方案数就是 $\binom{siz_u+siz_v-i-k}{siz_u-i}$
这样朴素的转移是 $O(n^3)$ 的，观察发现我们每次的 $j$ 要满足 $j\leq k$，所以对于 $f[v][j]$ 求前缀和就可以把复杂度做到 $O(n^2)$ 了。
对于 $u$ 在 $v$ 之前的情况，类似的方法。
但是注意我们需要另外开一个数组来做转移，否则会被反复更新。
**code**
```
#include <bits/stdc++.h>
using namespace std;
# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)
typedef long long ll;
const int N=1005;
const int mod=1e9+7;
template<typename T> void read(T &x){
x=0;int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
x*=f;
}
int t,n;
int head[N],cnt;
int siz[N];
int f[N][N],g[N],h[N];
int fac[N],inv[N];
struct Edge{
int to,next,w;
}e[N<<1];
void add(int x,int y,int c){
e[++cnt]=(Edge){y,head[x],c},head[x]=cnt;
}
int Qpow(int base,int ind){
int res=1;
while(ind){
if(ind&1)res=1ll*res*base%mod;
base=1ll*base*base%mod;
ind>>=1;
}
return res;
}
int C(int n,int m){
return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
void dfs(int u,int fa){
siz[u]=1;
f[u][1]=1;
RepG(en,u){
int v=e[en].to;
if(v==fa)continue;
dfs(v,u);
Rep(i,1,siz[u]+siz[v])h[i]=0;
if(e[en].w<0){
g[0]=0;
Rep(j,1,siz[v])(g[j]=g[j-1]+f[v][j])%=mod;
Rep(i,1,siz[u])
Rep(k,1,siz[v])
(h[i+k]+=1ll*f[u][i]*g[k]%mod*C(i+k-1,i-1)%mod*C(siz[u]+siz[v]-i-k,siz[u]-i)%mod)%=mod;
}
else{
g[siz[v]+1]=0;
_Rep(j,siz[v],1)(g[j]=g[j+1]+f[v][j])%=mod;
Rep(i,1,siz[u])
Rep(k,0,siz[v])
(h[i+k]+=1ll*f[u][i]*g[k+1]%mod*C(i+k-1,i-1)%mod*C(siz[u]+siz[v]-i-k,siz[u]-i)%mod)%=mod;
}
siz[u]+=siz[v];
Rep(i,1,siz[u])f[u][i]=h[i];
}
}
int main()
{
read(t);
fac[0]=inv[0]=1;
Rep(i,1,1000)fac[i]=1ll*fac[i-1]*i%mod;
Rep(i,1,1000)inv[i]=Qpow(fac[i],mod-2);
while(t--){
memset(head,-1,sizeof(head)),cnt=0;
memset(f,0,sizeof(f));
read(n);
Rep(i,1,n-1){
int x,y;
char opt[10];
scanf("%d%s%d",&x,opt,&y);
x++,y++;
if(opt[0]=='<')add(x,y,1),add(y,x,-1);
else add(x,y,-1),add(y,x,1);
}
dfs(1,0);
int ans=0;
Rep(i,1,n)(ans+=f[1][i])%=mod;
printf("%d\n",ans);
}
return 0;
}
```