欢迎来到塞莱斯特山[jzoj6506]

发表于 分类于

题意

problem

题解

首先，因为是在一棵树上，我们不妨考虑的是树形DP。那么来看一棵子树应该如何设计状态。

子树 $u$ 中的点在排列上形成了若干个不相交的段。在DP的时候我们需要合并$u$ 的子树的结果，也就是将若干个段合成几个段。如果两个不同子树的段在这时合成了一段，那么这两个段的衔接处就会产生一个 $dep_u$ 的贡献。

因此，我们可以设计状态为 $f_{u,i}$ 表示考虑子树 $u$ 时，一共有 $i$ 个段，段与段之间有序的方案数。

那么考虑枚举 $u$ 的子树 $v$，然后将贡献合并到 $u$ 那里去。

枚举 $i,j,k$，有

$$f’{u,k}=\sum{i}\sum_{j}f_{u,i}\times f_{v,j}\times g_{i,j,k}\times dep_u^{i+j-k}$$

其中，$g_{i,j,k}$ 为将两种不同的段，第一种有 $i$ 个段，第二种有 $j$ 个，合并成 $k$ 个段的方案数（段与段之间有序）。

那么，枚举合并之后 $k$ 个段中，第一个段是怎么来的。分三种情况讨论，得到：

$$g_{i,j,k}=(2\times \sum_{l=1}g_{i-l,j-l,k-1})+\sum_{l=0}g_{i-l,j-l-1,k-1}+\sum_{l=0}g_{i-l-1,j-l,k-1}$$

发现这三个都是一个前缀和的形式，用前缀和优化一下即可达到 $O(n^3)$ 的预处理。

时间复杂度 $O(n^3)$。

注意树上背包的时候需要按照子树大小来搞，不然复杂度不对。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const ll mod=1e9+7;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y)
{
	y%=(mod-1);ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1) ans=ans*x%mod;
	return ans;
}
const int N=505;
int n;
vector<int> adj[N];
int dep[N],siz[N];
ll f[N][N],h[N],s[N<<1][N],pw[N][N];
int g[N][N][N];
void dfs(int u)
{
	siz[u]=1; f[u][1]=1;
	for(auto v:adj[u])
	{
		dep[v]=dep[u]+1;
		dfs(v);
		fo(i,1,siz[u])
			fo(j,1,siz[v])
				fo(k,max(i-j,1),i+j)
					h[k]=Add(h[k],Mul(f[u][i]*f[v][j]%mod,pw[dep[u]][i+j-k]*g[i][j][k]%mod));
		siz[u]+=siz[v];
		fo(i,0,siz[u]) f[u][i]=h[i];
		fo(i,0,n) h[i]=0;
	}
}

int main()
{
	FO(tree);
	n=read();
	fo(i,2,n) adj[read()].pb(i);
	g[0][0][0]=1;
	int m=n+2;
	fo(k,1,n)
	{
		fo(i,0,n)
			fo(j,0,n-i)
			{
				if(i+j>=k) g[i][j][k]=(s[i-j+m][k-1]*2%mod+(s[i-j+1+m][k-1]+s[i-j-1+m][k-1]))%mod;
				s[i-j+m][k-1]=Add(s[i-j+m][k-1],g[i][j][k-1]);
			}
		pw[k][0]=1;
		fo(i,1,n) pw[k][i]=pw[k][i-1]*k%mod;
	}
	dep[1]=1;
	dfs(1);
	printf("%d",f[1][1]);
	return 0;
}