bzoj 3170
题意：给定一个树形图，求他的拓扑序个数。
如果看成拓扑图做那就凉了…据说拓扑图的拓扑序个数是NP的
我们发现这里是一个树形图，那么我们考虑分类讨论边的方向，树形DP
DP是合并思想，最暴力的想法就是，每个点存下一个序列，然后在父亲$u$合并儿子的答案。
具体就是$dp(u) \Leftarrow dp’(u), dp(v)$ ($dp’(u)$为只考虑当前枚举的$v$前的子树，类似DP求树直径方法)
但是显然不能记录那么多，我们考虑设$dp(u, i)$为$u$子树形成的拓扑序，$u$在$i$位置的方案数。这个状态可以让我们知道$u$前有几个数，$u$后有几个数。(以上思想是思考DP不要拘束于状态，而是去想怎么方便怎么做，之后再来看怎么压状态)
考虑$dp(u, i) \Leftarrow dp’(u, j), dp(v, k)$
那么先给出式子(先考虑$u$在$v$前的情况)
$$
dp(u,i)=\sum_{j=1}^{\min(\text{sz}[i], i)} C^{j-1}_{i-1} \cdot C^{\text{sz}[u]-j}_{\text{sz}[u]+\text{sz}[v]-i} \cdot dp’(u,j) \cdot \sum_{k=i-j+1}^{\text{sz}[v]}dp(v, k)
$$
这里是$dp(u, i) \Leftarrow dp’(u, j), dp(v, k)$，即一个序列合并的情况。
前$3$项是说，在$u$的前面的$i-1$个位置，选择$j-1$个位置出来，然后在$u$后面$\text{sz}[u]+\text{sz}[v]-i$个位置选$\text{sz}[u]-j$个位置出来，这些选的位置只有$dp’(u,j)$种填法(保证顺序)。然后其他空位置只能有$dp(v, k)$种填法。注意对于$v$合并后必须到$u$后面，所以对$k$有约束。
然后对于$u$在$v$后，就是$k$的约束不同。然后就可以DP了。
对于复杂度，我们先发现后面$v,k$的东西可以单独前缀和处理，然后前面的$i,j$在$\text{LCA}$处计算复杂度，是$O(n^2)$的。
具体就是，这里相当于枚举$v$前子树和$v$子树的节点，设这一对点为$(a,b)$，这对点当且仅当在$\text{LCA}$处被枚举，所以不会重复枚举，点对个数为$n^2$，类似此题分析的还有很多树形DP题。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
int T;
namespace flyinthesky {
const int MAXN = 1000 + 5;
const LL MO = 1000000007;
int n, en, hd[MAXN], sz[MAXN];
struct edge {int u, v, d, nxt;} ed[MAXN * 2]; // d = 0, u < v
LL C[MAXN][MAXN], dp[MAXN][MAXN], pre[MAXN][MAXN], suf[MAXN][MAXN];
void ins(int u, int v, int d) {ed[++en] = (edge){u, v, d, hd[u]}, hd[u] = en;}
void dfs(int u, int fa) {
sz[u] = 1;
dp[u][1] = 1;
for (int o = hd[u]; o >= 0; o = ed[o].nxt) {
edge &e = ed[o];
if (e.v != fa) {
dfs(e.v, u);
if (ed[o].d == 0) {
for (int i = sz[u] + sz[e.v]; i; --i) {
LL sum = 0;
for (int j = 1; j <= min(sz[u], i); ++j) {
sum = (sum + C[i - 1][j - 1] * dp[u][j] % MO * C[sz[u] + sz[e.v] - i][sz[u] - j] % MO * suf[e.v][i - j + 1] % MO) % MO;
}
dp[u][i] = sum;
}
} else {
for (int i = sz[u] + sz[e.v]; i; --i) {
LL sum = 0;
for (int j = 1; j <= min(sz[u], i); ++j) {
sum = (sum + C[i - 1][j - 1] * dp[u][j] % MO * C[sz[u] + sz[e.v] - i][sz[u] - j] % MO * pre[e.v][i - j] % MO) % MO;
}
dp[u][i] = sum;
}
}
sz[u] += sz[e.v];
}
}
for (int i = 1; i <= sz[u]; ++i) pre[u][i] = (dp[u][i] + pre[u][i - 1]) % MO;
for (int i = sz[u]; i; --i) suf[u][i] = (dp[u][i] + suf[u][i + 1]) % MO;
}
void clean() {
en = -1, ms(hd, -1), ms(sz, 0), ms(dp, 0), ms(pre, 0), ms(suf, 0);
}
int solve() {
clean();
scanf("%d", &n);
for (int u, v, i = 1; i < n; ++i) {
char c;
scanf("%d %c %d", &u, &c, &v), ++u, ++v;
if (c == '<') ins(u, v, 0), ins(v, u, 1);
else ins(u, v, 1), ins(v, u, 0);
}
dfs(1, 0);
LL ans = 0;
for (LL i = 1; i <= n; ++i) ans = (ans + dp[1][i]) % MO;
printf("%lld\n", ans);
return 0;
}
}
int main() {
for (int i = 0; i <= 1000; ++i) flyinthesky::C[i][0] = flyinthesky::C[i][i] = 1;
for (int i = 1; i <= 1000; ++i)
for (int j = 1; j < i; ++j) flyinthesky::C[i][j] = (flyinthesky::C[i - 1][j] + flyinthesky::C[i - 1][j - 1]) % flyinthesky::MO;
cin >> T;
while (T--) flyinthesky::solve();
return 0;
}
