题解 P4099 【[HEOI2013]SAO 】

2019-04-26 17:02:13


树形 $\mathrm{DP}$ 。

显然所有限制条件构成一个树形图,考虑以 $1$ 为根跑 $\mathrm{DP}$ 。

设 $f[i][j]$ 表示以 $i$ 为根的子树, $i$ 在子树内排名为 $j$ 的方案数。

转移的话,每次把一颗子树 $v$ 合并进来,也就是把 $f[v][k]$ 算到 $f[u][i]$ 里去。分两种情况:

  • $v$ 在 $u$ 的前面

枚举一个 $j$ 表示 $v$ 的子树中有 $j$ 个在 $u$ 前面。

那么当前的方案数是 $C_{i+j-1}^{i-1}\times f[u][i]\times f[v][k]\times C_{sz[u]+sz[v]-i-j}^{sz[u]-i}$ ,把它累加到 $f[u][i+j]$ 里去。

考虑怎么优化转移。现在的转移是这个样子(忽略 $\mathrm{long\ long}$ 的问题):

for (re int i=1;i<=sz[u];++i)
    for (re int k=1;j<=sz[v];++k)
        for (re int j=k;j<=sz[v];++j)
            add(f[u][i+j],f[u][i]*f[v][k]*C[i+j-1][i-1]*C[sz[u]+sz[v]-i-j][sz[u]-i]);

把 $j$ 和 $k$ 换一下,变成:

for (re int i=1;i<=sz[u];++i)
    for (re int j=1;j<=sz[v];++j)
        for (re int k=1;k<=j;++k)
            add(f[u][i+j],f[u][i]*f[v][k]*C[i+j-1][i-1]*C[sz[u]+sz[v]-i-j][sz[u]-i]);

那么只要记一下 $f[v]$ 的前缀和就能去掉 $k$ 那一维,实现 $O(1)$ 转移了。

  • $v$ 在 $u$ 的后面

和上面的情况类似:

for (re int i=1;i<=sz[u];++i)
    for (re int j=0;j<=sz[v];++j)
        for (re int k=i+1;k<=sz[v];++k)
            add(f[u][i+j],f[u][i]*f[v][k]*C[i+j-1][i-1]*C[sz[u]+sz[v]-i-j][sz[u]-i]);

记 $f[v]$ 的后缀和同样能够实现 $O(1)$ 转移。


最后的答案为 $\sum\limits_{i=1}^nf[1][i]$ 。总时间复杂度为 $O(n^2)$ 。

具体实现及细节见代码