洛谷 4099 「HEOI2013」SAO

注意到把边当成无向边就是棵树，以下提到这棵树的地方将会加上「」以区分。

考虑设 fu,i 表示「以 u 为根的子树」的导出子图的所有拓扑序列中，u 放在第 i 位的方案数。
转移时考虑增加一个儿子 v 的贡献，设 f′u,i 表示增加 v 的贡献之后的 f。

若 v 必在 u 之前，枚举 u 原来的排名 j 和 v 原来的排名 k，则需从「以 v 为根的子树」中取 i−j 个放在 u 之前（必包含 v），有 f′u,i=min(i−1,sizeu)∑j=1i−j∑k=1fu,jfv,k(i−1j−1)(sizeu+sizev−isizeu−j)

其中 sizeu 表示「v 之前的子树」的大小，sizev 表示「以 v 为根的子树」的大小。
注意到这是一个 O(n3) 的转移，然而用前缀和优化即可。

v 在 u 之后的限制类似。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e3;
const int mod = 1e9 + 7;
int T,n;
int C[N + 5][N + 5];
int to[(N << 1) + 5],val[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5],edge_tot;
inline void add(int u,int v,int w)
{
    int &tot = edge_tot;
    to[++tot] = v,val[tot] = w,pre[tot] = first[u],first[u] = tot;
}
int fa[N + 5],sz[N + 5],f[N + 5][N + 5],g[N + 5],s[N + 5];
void dfs(int p)
{
    sz[p] = f[p][1] = 1;
    for(register int i = first[p];i;i = pre[i])
        if(to[i] ^ fa[p])
        {
            fa[to[i]] = p,dfs(to[i]);
            memset(g,0,sizeof g);
            if(val[i])
            {
                s[0] = 0;
                for(register int j = 1;j <= sz[to[i]];++j)
                    s[j] = (s[j - 1] + f[to[i]][j]) % mod;
                for(register int j = 1;j <= sz[p] + sz[to[i]];++j)
                    for(register int k = 1;k <= min(j - 1,sz[p]);++k)
                        g[j] = (g[j] + (long long)f[p][k] * s[j - k] % mod * C[j - 1][k - 1] % mod * C[sz[p] + sz[to[i]] - j][sz[p] - k]) % mod;
            }
            else
            {
                s[sz[to[i]] + 1] = 0;
                for(register int j = sz[to[i]];j;--j)
                    s[j] = (s[j + 1] + f[to[i]][j]) % mod;
                for(register int j = 1;j <= sz[p] + sz[to[i]];++j)
                    for(register int k = 1;k <= min(j,sz[p]);++k)
                        g[j] = (g[j] + (long long)f[p][k] * s[j - k + 1] % mod * C[j - 1][k - 1] % mod * C[sz[p] + sz[to[i]] - j][sz[p] - k]) % mod;
            }
            sz[p] += sz[to[i]];
            for(register int j = 1;j <= sz[p];++j)
                f[p][j] = g[j];
        }
}
int ans;
int main()
{
    for(register int i = 0;i <= N;++i)
        C[i][0] = 1;
    for(register int i = 1;i <= N;++i)
        for(register int j = 1;j <= i;++j)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    scanf("%d",&T);
    for(;T;--T)
    {
        scanf("%d",&n),ans = edge_tot = 0;
        memset(first,0,sizeof first);
        int u,v;
        char w;
        for(register int i = 2;i <= n;++i)
            scanf("%d %c%d",&u,&w,&v),++u,++v,add(u,v,w == '>'),add(v,u,w == '<');
        dfs(1);
        for(register int i = 1;i <= n;++i)
            ans = (ans + f[1][i]) % mod;
        printf("%d\n",ans);
    }
}