JZOJ 6506 欢迎来到塞莱斯特山

第一次见这种 DP 方式，好神仙……

考虑设 fu,i 表示 u 子树内的点确定了排列中的 i 个相对位置确定的，不相邻的连续段时这些连续段的贡献。
则考虑使用类似背包的转移方式，逐个儿子地合并答案。

考虑如何合并 fu,j 与 fv,k 至 fu,i，其中 v 为 u 的一个儿子。
由于相对位置确定且不相邻，所以合并后会有 j+k−i 对相邻的位置产生贡献；而显然其 LCA 均为 u，故贡献为 fu,j⋅fv,k⋅gi,j,k⋅depj+k−iu

其中 gi,j,k 表示将 j 个相对位置确定且不相邻的连续段和 k 个相对位置确定且不相邻的连续段合并为 i 个相对位置确定且不相邻的连续段的方案数。
这个也可以 DP 出来，具体是枚举这 i 个连续段的第一个连续段由 j,k 个连续段中各多少个组成，则 gi,j,k=min{j,k}∑u=12gi−1,j−u,k−u+min{j−1,k}∑u=0gi−1,j−u−1,k−u+min{j,k−1}∑u=0gi−1,j−u,k−u−1

然而这样需要 O(n4) 预处理，这就很不爽了。
但是注意到转移过来的状态的 j−k 的值都是确定的，所以考虑用前缀和的方式维护，注意不要计入超出范围的贡献。

代码：

#include <cstdio>
#define add(x,y) (x + y >= mod ? x + y - mod : x + y)
#define dec(x,y) (x < y ? x - y + mod : x - y)
using namespace std;
const int N = 500;
const int mod = 1e9 + 7;
int n,inv[N + 5];
int to[N + 5],pre[N + 5],first[N + 5];
inline void add_edge(int u,int v)
{
    static int tot = 0;
    to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
int f[N + 5][N + 5],g[N + 5][N + 5][N + 5],t[N + 5],s_[N + 5][(N << 1) + 10],*s[N + 5];
int fa[N + 5],dep[N + 5],sz[N + 5];
void dfs(int p)
{
    sz[p] = f[p][1] = 1;
    for(register int i = first[p];i;i = pre[i])
    {
        dep[to[i]] = dep[p] + 1,dfs(to[i]);
        for(register int j = 1;j <= sz[p] + sz[to[i]];++j)
            t[j] = f[p][j],f[p][j] = 0;
        for(register int j = 1,pw1 = inv[dep[p]];j <= sz[p] + sz[to[i]];++j,pw1 = (long long)pw1 * inv[dep[p]] % mod)
            for(register int k = 0,pw2 = pw1;k <= sz[p];++k,pw2 = (long long)pw2 * dep[p] % mod)
                for(register int l = 0,pw3 = pw2;l <= sz[to[i]];++l,pw3 = (long long)pw3 * dep[p] % mod)
                    f[p][j] = (f[p][j] + (long long)t[k] * f[to[i]][l] % mod * g[j][k][l] % mod * pw3 % mod) % mod;
        sz[p] += sz[to[i]];
    }
}
int main()
{
    freopen("tree.in","r",stdin),freopen("tree.out","w",stdout);
    scanf("%d",&n),g[0][0][0] = inv[1] = 1;
    for(register int i = 0;i <= n;++i)
        s[i] = s_[i] + N + 5;
    for(register int i = 2;i <= n;++i)
        inv[i] = (long long)(mod - mod / i) * inv[mod % i] % mod;
    for(register int i = 1;i <= n;++i)
        for(register int j = 0;j <= n;++j)
            for(register int k = 0;k <= n - j;++k)
                g[i][j][k] = add(g[i][j][k],add(s[i - 1][j - k],s[i - 1][j - k])),
                g[i][j][k] = add(g[i][j][k],s[i - 1][j - k - 1]),
                g[i][j][k] = add(g[i][j][k],s[i - 1][j - k + 1]),
                s[i - 1][j - k] = add(s[i - 1][j - k],g[i - 1][j][k]);
    for(register int i = 2;i <= n;++i)
        scanf("%d",fa + i),add_edge(fa[i],i);
    dep[1] = 1,dfs(1);
    printf("%d\n",f[1][1]);
}