DP、组合

计数题就很不会，听 jzp 讲之后勉强懂了。

题目大意：给一棵树，需要给所有点填入一个排列，使得每条边给的大小关系都得到满足，求方案数。

这种题除了 DP 我也考虑不到什么其它解法。

记 $f_{u, i}$ 表示在 $u$ 的前 $j$ 个子树中，$u$ 的排名为 $i$ 的方案数，注意状态中是 $u$ 的排名为 $i$ 而非 $u$ 的取值。

对于每一个儿子 $v$，我们需要思考的就是如何从 $f_{v, j}$ 转移到 $f_{u, i}$。考虑枚举 $i \in \left[1, s_u\right]$、$j \in \left[1, s_v\right]$ 其中 $s$ 数组代表子树大小，这里 $s_v$ 不算在 $s_u$ 里。

以 $u,v$ 间的边边权为 < 为例。直接转移不好做，考虑再枚举一维 $k \in [0, j - 1]$ 代表 $v$ 前面的 $j - 1$ 个数中有 $k$ 个排名在 $u$ 前面。那么转移就变成 $f_{u, i}$ 和 $f_{v, j}$ 一起转移到 $f_{u, i + k}$。接下考虑计算方案数，$u$ 前面有 $i + k - 1$ 个数，其中 $k$ 个在 $v$ 的子树中，那么方案数为 $\binom{i + k - 1}{k}$。同理 $i$ 之后有 $s_u - i + s_v - k$ 个数，其中 $s_v - k$ 个在 $v$ 的子树中，所以有方案数 $\binom{s_u - i + s_v - k}{s_v - k}$。

得出转移方程：

$$f_{u, i + k} = \sum_{i = 1} ^ {s_u} \sum_{j = 1} ^ {s_v}\sum_{k = 0} ^ {j - 1} f_{u, i} \times f_{v, j} \times \binom{i + k - 1}{k}\binom{s_u - i + s_v - k}{s_v - k}$$

然而这样时间复杂度为 $\mathcal{O}\left(n^3\right)$，需要优化。

观察到 $j$ 这一维所涉变量只有 $f_{v, j}$，所以考虑把 $j$ 放到最里面并把 $f_{v, j}$ 提出来。

$$\begin{align*} f_{u, i + k} &= \sum_{i = 1} ^ {s_u}\sum_{k = 0} ^ {s_v - 1 } \sum_{j = k + 1} ^ {s_v}f_{u, i} \times f_{v, j} \times \binom{i + k - 1}{k}\binom{s_u - i + s_v - k}{s_v - k}\\ &= \sum_{i = 1} ^ {s_u}\sum_{k = 0} ^ {s_v - 1 } \left( \sum_{j = k + 1} ^ {s_v} f_{v, j} \right)f_{u, i} \times \binom{i + k - 1}{k}\binom{s_u - i + s_v - k}{s_v - k} \end{align*}$$

中间那一坨前缀和可以解决。

边权为 > 的同理。

$$\begin{align*} f_{u, i + k} &= \sum_{i = 1} ^ {s_u} \sum_{j = 1} ^ {s_v}\sum_{k = j} ^ {s_v} f_{u, i} \times f_{v, j} \times \binom{i + k - 1}{k}\binom{s_u - i + s_v - k}{s_v - k}\\ &= \sum_{i = 1} ^ {s_u}\sum_{k = 1} ^ {s_v } \left( \sum_{j = 1} ^ {k} f_{v, j} \right)f_{u, i} \times \binom{i + k - 1}{k}\binom{s_u - i + s_v - k}{s_v - k} \end{align*}$$

值得注意的是状态定义时我们默认滚掉了一维（即表示在 $u$ 的前 $j$ 个子树中这一维），故方程中的 $f_{u, i}$ 应在转移前复制到一个新数组 $g$ 中进行转移。

时间复杂度 $\mathcal{O}\left(n^2\right)$，足以通过此题。

:::info[code]

// 主观感受是轻微压行，轻喷 
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define inf 0x3f3f3f3f3f3f3f3f
#define F(x, v) for (auto x : (v))
#define ALL(x) (x).begin(), (x).end()
#define L(i, a, b) for (register int i = (a); i <= (b); i++)
#define R(i, a, b) for (register int i = (a); i >= (b); i--)
#define FRE(x) freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout)
using namespace std;

inline int cmax(int& x, int c) { return x = max(x, c); }
inline int cmin(int& x, int c) { return x = min(x, c); }
bool bgmem;
int _test_ = 1, cas;

namespace zrh {
	const int N = 3005, mod = 1e9 + 7;
	struct ed { int v; bool op; };
	int n, dp[N][N], pre[N][N], sz[N], c[N][N], f[N];
	vector< ed > g[N];
	void dfs(int u, int fa) {
		sz[u] = 1, dp[u][1] = 1; // 因为最开始只有 u 一个点，所以初始化 f[u][1] = 1 
		F(p, g[u]) { int v = p.v; bool op = p.op; if (v != fa) {
			dfs(v, u);
			L(i, 1, sz[u]) f[i] = dp[u][i], dp[u][i] = 0; // 复制一遍 f[u] 
			if (!op) L(i, 1, sz[u]) L(k, 0, min(sz[v] - 1, n - i)) // 当 u < v 
				dp[u][i + k] = (dp[u][i + k] + f[i] * (pre[v][sz[v]] - pre[v][k] + mod) % mod * c[i + k - 1][k] % mod * c[sz[u] + sz[v] - k - i][sz[v] - k] % mod) % mod;
			else L(i, 1, sz[u]) L(k, 1, min(sz[v], n - i)) // 当 u > v 
				dp[u][i + k] = (dp[u][i + k] + f[i] * pre[v][k] % mod * c[i + k - 1][k] % mod * c[sz[u] + sz[v] - k - i][sz[v] - k] % mod) % mod;
			sz[u] += sz[v]; // 更新 s[u] 
		}}
		L(i, 1, sz[u]) pre[u][i] = (pre[u][i - 1] + dp[u][i]) % mod; // 计算前缀和 
	}
    void init() {
    	L(i, 0, N - 5) {
    		c[i][0] = 1;
    		L(j, 1, i) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod; // 杨辉三角预处理组合数 
		}
	}
    void clear() {}
    void solve() {
    	cin >> n;
    	L(i, 2, n) {
    		int e; char c; cin >> e >> c;
    		g[e].push_back({i, (c == '>')});
    		g[i].push_back({e, (c == '<')});
		}
		dfs(1, 0);
		cout << pre[1][sz[1]] << "\n";
	}
}  // namespace zrh

bool edmem;
signed main() {
//    FRE("follow"); 
	ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
//    cin >> _test_;
    zrh::init();
    while (++cas <= _test_) zrh::clear(), zrh::solve();
    cerr << "memory: " << fabs(&edmem - &bgmem) / 1024 / 1024 << "MB\n";
    cerr << "time  : " << (double)clock() * CLOCKS_PER_SEC / 1000 << "ms\n";
    return 0;
}
// 成熟时暗恋 zrh 

:::