3167: [Heoi2013]Sao

题意：

n个点的“有向”树，求拓扑排序方案数

---

Welcome to Sword Art Online!!!

一开始想错了...没有考虑一个点的孩子可以排在父亲后...

为了能转移，给状态加一维，\(f[i][j]\)表示子树i，i排在第j位的方案数

然后，很像树形背包啊，转移枚举孩子子树中k个点在i之前，更新\(f[i][j+k]\)

严格做到每次合并复杂度为 “已经合并大小*正要合并进去的大小”，那么这个复杂度就是\(O(n^2)\)的，因为一个点对只贡献一次

真不敢相信我以前的树形背包都写的是\(O(n^3)\)

注意需要用一个新数组保存当前更新得到的值

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N = 1005, P = 1e9+7;

inline int read() {

    char c=getchar(); int x=0,f=1;

    while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}

    while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}

    return x*f;

}

int n, u, v, c[N][N];

char s[5];

struct edge{int v, ne, p;} e[N<<1];

int cnt, h[N];

inline void ins(int u, int v) { //printf("ins %d %d\n", u, v);

	e[++cnt] = (edge){v, h[u], 1}; h[u] = cnt;

	e[++cnt] = (edge){u, h[v], 0}; h[v] = cnt;

}

int f[N][N], size[N], f_pre[N][N], f_suf[N][N], g[N];

void dp(int u, int fa) {

	size[u] = 1; f[u][1] = 1;

	for(int i=h[u]; i; i=e[i].ne) {

		int v = e[i].v, p = e[i].p;

		if(v == fa) continue;

		dp(v, u);

		for(int j = 0; j <= size[u] + size[v]; j++) g[j] = 0;

		for(int j = 1; j <= size[u]; j++)

			for(int k = 0; k <= size[v]; k++) {

				ll t = p ? f_suf[v][k+1] : f_pre[v][k];

				g[j+k] = (g[j+k] + (ll) c[j-1+k][k] * c[size[u]-j+size[v]-k][size[v]-k] %P * f[u][j] %P * t) %P;

			}

		for(int j = 0; j <= size[u] + size[v]; j++) f[u][j] = g[j];

		size[u] += size[v];

	}

	for(int i = 1; i <= size[u]; i++) f_pre[u][i] = (f_pre[u][i-1] + f[u][i]) %P;

	for(int i = size[u]; i >= 1; i--) f_suf[u][i] = (f_suf[u][i+1] + f[u][i]) %P;

}

int main() {

    freopen("in", "r", stdin);

	int T = read();

	c[0][0] = 1;

	for(int i=1; i<N; i++) {

		c[i][0] = 1;

		for(int j=1; j<N; j++) c[i][j] = (c[i-1][j] + c[i-1][j-1]) %P;

	}

	while(T--) {

		n = read();

		memset(f, 0, sizeof(f));

		memset(f_pre, 0, sizeof(f_pre));

		memset(f_suf, 0, sizeof(f_suf));

		cnt = 0; memset(h, 0, sizeof(h));

		for(int i=1; i<n; i++) {

			u = read()+1; scanf("%s", s); v = read()+1;

			if(s[0] == '<') ins(u, v); else ins(v, u);

		}

		dp(1, 0);

		printf("%d\n", f_pre[1][size[1]]);

	}

}