HDU5370 Tree Maker 题解
link
首先，考虑我们如果没有限制，即只单纯地给你 \(n\) 个点，让你构树，求树的形状总数有多少种。这个问题其实就是 Catalan 数列地第 \(n\) 项。证明：枚举根的 dfn 序，写出 dp 式，发现就是 Catalan 的基本式子。
现在回到本题，发现出题人限制了有些边必须加上。所以我们考虑 dp。令 \(dp_{i,j}\) 为父亲节点给了当前 \(i\) 节点 \(j\) 个名额的方案数。其实就是一个树上背包。这里“名额”的理解是：父节点 \(fa\) 建树时出题人说他应该要建 \(x_{fa}\) 个点，那么减去 \(fa\) 这个点，剩下的两个子树必须摊掉 \(x_{fa}-1\) 个点，所以我们每次 dfs 往下递归分配这个点数。
注意：如果 \(x\) 这个点本身有名额，就不能从 \(fa\) 往下传名额，因为 \(x\) 是在 \(fa\) 后建立的。
转移方程：\(dp_{i,j}=\sum_{k=0}^{j+val_i}dp_{son0,k}\times dp_{son1,j+val_i-k}\)。
然后其实就做完了，打记搜 \(\mathcal {O}(n^3)\)。
但是这道题卡常，所以如果 \(fa\) 节点的任何一个子节点本身建树时有名额，我们可以省去 \(\mathcal {O}(n)\) 的转移时间，详见代码。
#include
#include
#include
#include
#include
#define LL long long
using namespace std;
// 傻逼总是那么多
const int MAXN = 505, Mod = 1000000007;
int n, Fa[MAXN], L[MAXN], R[MAXN], jc[MAXN << 1], inv[MAXN << 1];
int val[MAXN], tot, Cat[MAXN];
LL dp[MAXN][MAXN];
int Qpow(int x, int y) {
int ans = 1;
for(; y; y >>= 1) {
if(y & 1) ans = (LL)ans * x % Mod;
x = (LL)x * x % Mod;
}
return ans;
}
int C(int x, int y) { return x < y ? 0 : (LL)jc[x] * inv[y] % Mod * inv[x - y] % Mod; }
void dfs(int x, int lasv) {
int wefuck = lasv;
// if(x) printf("*%d %d %d*\n", x, L[x], R[x]);
lasv += val[x];
if(!x) {
if(lasv == 0) dp[x][wefuck] = 1;
else dp[x][wefuck] = Cat[lasv];
return;
}
lasv --;
if(lasv < 0) { dp[x][wefuck] = 0; return; }
if(~dp[x][wefuck]) return;
dp[x][wefuck] = 0;
if(val[L[x]] && val[R[x]]) {
if(lasv) return;
dfs(L[x], 0); dfs(R[x], 0);
dp[x][wefuck] = (dp[x][wefuck] + dp[L[x]][0] * dp[R[x]][0]) % Mod;
return;
}
else if(val[L[x]]) {
dfs(L[x], 0); dfs(R[x], lasv);
dp[x][wefuck] = (dp[x][wefuck] + dp[L[x]][0] * dp[R[x]][lasv]) % Mod;
}
else if(val[R[x]]) {
dfs(L[x], lasv); dfs(R[x], 0);
dp[x][wefuck] = (dp[x][wefuck] + dp[L[x]][lasv] * dp[R[x]][0]) % Mod;
}
else {
for(int i = 0; i <= lasv; i ++) {
dfs(L[x], i); dfs(R[x], lasv - i);
dp[x][wefuck] = (dp[x][wefuck] + dp[L[x]][i] * dp[R[x]][lasv - i]) % Mod;
// printf("%d %d %d %d %d %d %d %d\n", x, lasv, L[x], i, dp[L[x]][i + val[L[x]] - 1], R[x], lasv - i, dp[R[x]][lasv - i + val[R[x]] - 1]);
}
}
// printf("%d %d %d\n", x, lasv, dp[x][wefuck]);
}
int main() {
int caser = 0, f, x, now = 0; jc[0] = 1;
for(int i = 1; i <= 1000; i ++) jc[i] = (LL)jc[i - 1] * i % Mod;
inv[1000] = Qpow(jc[1000], Mod - 2);
for(int i = 999; i >= 0; i --) inv[i] = (LL)inv[i + 1] * (i + 1) % Mod;
for(int i = 0; i <= 500; i ++) Cat[i] = (C(2 * i, i) - C(2 * i, i - 1)) % Mod;
while(scanf("%d", &n) == 1) {
memset(val, 0, sizeof(val)); memset(L, 0, sizeof(L)); memset(R, 0, sizeof(R));
memset(dp, -1, sizeof(dp)); tot = 1; now = 1; val[1] = 1; memset(Fa, 0, sizeof(Fa));
for(int i = 1; i <= n; i ++) {
scanf("%d", &f);
if(f == 0) now = Fa[now];
if(f == 1) {
if(!L[now]) L[now] = ++ tot, Fa[tot] = now;
now = L[now];
}
if(f == 2) {
if(!R[now]) R[now] = ++ tot, Fa[tot] = now;
now = R[now];
}
if(f == 3) scanf("%d", &x), tot ++, val[tot] = x, L[now] = tot, Fa[tot] = now;
if(f == 4) scanf("%d", &x), tot ++, val[tot] = x, R[now] = tot, Fa[tot] = now;
}
dfs(1, 0); printf("Case #%d: %lld\n", ++ caser, (dp[1][val[1] - 1] + Mod) % Mod);
}
return 0;
}