6506. 【GDOI2020模拟03.11】欢迎来到塞莱斯特山（tree）

题目描述

题解

区间合并dp，之前做过但是忘了

两个子树合并时，一定是若干段区间交错，如果有相邻两段来自不同子树的区间就可以合并，此时的深度贡献为d[t]

设f[i][j]表示根i段j，g[i][j][k][0/1]表示当前合并时剩余总段i，两个子树的段jk，结尾为什么

看似O(n^4)，实际同子树背包可以减一个n

code

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define add(a,b) a=((1ll*a)+(b))%1000000007
#define min(a,b) (a<b?a:b)
#define mod 1000000007
#define ll long long
#define file
using namespace std;

int f[501][501],g[501][501][501][2],d[501],a[501][2],ls[501],size[501],n,i,j,k,l,len;

void New(int x,int y)
{
	++len;
	a[len][0]=y;
	a[len][1]=ls[x];
	ls[x]=len;
}

void dfs(int t)
{
	int I,i,j,k,l,s,x;
	f[t][1]=size[t]=1;
	
	for (I=ls[t]; I; I=a[I][1])
	{
		x=a[I][0];d[x]=d[t]+1;
		dfs(x);
		
		fo(i,1,size[t])
		{
			fo(j,1,size[x])
			g[i+j][i-1][j][0]=g[i+j][i][j-1][1]=1ll*f[t][i]*f[x][j]%mod;
		}
		
		fd(i,size[t]+size[x],1)
		{
			fd(j,size[t],0)
			{
				fd(k,size[x],0)
				{
					fo(l,0,1)
					{
						if (j)
						{
							add(g[i][j-1][k][0],g[i][j][k][l]);
							if (l==1)
							add(g[i-1][j-1][k][0],1ll*g[i][j][k][l]*d[t]);
						}
						if (k)
						{
							add(g[i][j][k-1][1],g[i][j][k][l]);
							if (l==0)
							add(g[i-1][j][k-1][1],1ll*g[i][j][k][l]*d[t]);
						}
					}
				}
			}
		}
		
		fo(i,1,size[t]+size[x])
		f[t][i]=(g[i][0][0][0]+g[i][0][0][1])%mod;
		
		fo(i,1,size[t]+size[x])
		{
			fo(j,0,size[t])
			{
				fo(k,0,size[x])
				g[i][j][k][0]=g[i][j][k][1]=0;
			}
		}
		size[t]+=size[x];
	}
}

int main()
{
	freopen("tree.in","r",stdin);
	#ifdef file
	freopen("tree.out","w",stdout);
	#endif
	
	scanf("%d",&n);
	fo(i,2,n)
	{
		scanf("%d",&j);
		New(j,i);
	}
	
	d[1]=1;
	dfs(1);
	
	printf("%lld
",f[1][1]);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}