洛谷 P6383 -『MdOI R2』Resurrection（DP）

高速公路上正是补 blog 的时候，难道不是吗/doge，难不成逆在高速公路上写题/jy

首先形成的图显然是连通图并且有 \(n-1\) 条边。故形成的图是一棵树。

我们考虑什么样的树能够得到。考虑以 \(n\) 为根，由于每个点的编号都小于其父亲这个条件的存在，我们每次断开一条边时，两个连通块中编号最大的点肯定是这两个连通块中深度最浅的节点。而显然，对于一条边 \((u,v)\)，如果 \(u\) 是 \(v\) 的父亲，那么断开 \((u,v)\) 时 \(v\) 肯定是所在连通块中深度最浅的节点，也就是说我们要为每个点 \(x\) 找一个祖先 \(p_x\)，满足断开 \(x\) 与其父亲的边时，\(p_x\) 为其父亲所在连通块中深度最浅的节点。

考虑什么样的序列 \(p\) 符合要求。打个表发现一条链的情况答案是卡特兰数（cartesian number bushi）。而卡特兰数刚好是由 \(n\) 个左括号和 \(n\) 个右括号组成的括号序列的数量，而括号序列中每对括号肯定是不能相交的——即，要么相离，要么互相包含。因此我们猜测一组 \(p\) 符合条件，当且仅当不存在两个 \(x,y\) 满足 \(p_x,p_y,x,y\) 依次存在祖先关系。事实上这个结论是正确的可惜我不会证。这样就可以 DP 了。考虑 \(dp_{i,j}\) 表示确定了 \(i\) 祖先（注意，这里与传统的 DP 不同，因为传统的 DP 一般都假设子树内的状态已经确定，而这题是假设祖先的状态已经确定）的 \(p\)，目前 \(i\) 还有 \(j\) 个祖先可以选择，有多少个钦定 \(i\) 子树内点的 \(p\) 的方法，考虑如何转移，我们枚举 \(p_i\) 是目前可行的点中，从下往上数的第几个，设为 \(c\)，那么这样在钦定 \(i\) 的儿子时会 ban 掉 \(c-1\) 个祖先，同时又会为 \(u\) 的儿子新增一个符合要求的祖先——\(u\)，因此我们有 \(dp_{u,j}=\sum\limits_{c=1}^j\prod\limits_{v\in\text{son}(u)}dp_{v,j-c+2}\)。这样直接转移是三方的，无法通过。不过注意到这个 \(\sum\) 可以用前缀和优化掉，具体来说我们设 \(dp_{u,j}=dp_{u,j-1}+\prod\limits_{v\in\text{son}(u)}dp_{v,j+1}\)，这样记忆化搜索一下复杂度即可达到平方。

为什么会有个 freopen 呢？因为这是场 mns 的赛题……

const int MAXN=3000;

const int MOD=998244353;

int n,hd[MAXN+5],to[MAXN*2+5],nxt[MAXN*2+5],ec=0;

void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}

int dp[MAXN+5][MAXN+5];

int calc(int x,int f,int k){

	if(~dp[x][k]) return dp[x][k];dp[x][k]=0;

	if(k>1) dp[x][k]=calc(x,f,k-1);int res=1;

	for(int e=hd[x];e;e=nxt[e]){

		int y=to[e];if(y==f) continue;

		res=1ll*res*calc(y,x,k+1)%MOD;

	} dp[x][k]=(dp[x][k]+res)%MOD;

	return dp[x][k];

}

int main(){

//	freopen("reflection.in","r",stdin);

//	freopen("reflection.out","w",stdout);

	scanf("%d",&n);

	for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),adde(u,v),adde(v,u);

	memset(dp,-1,sizeof(dp));int res=1;

	for(int e=hd[n];e;e=nxt[e]){int y=to[e];res=1ll*res*calc(y,n,1)%MOD;}

	printf("%d\n",res);

	return 0;

}

巴特西

洛谷 P6383 -『MdOI R2』Resurrection（DP）

最新文章

热门文章