Problem Link

题目大意

给定 $n$ 个节点的树，保证父亲节点编号小于儿子，求有多少 $n+m$ 个节点的树（根节点为 $1$），使得：

• 对于所有 $i,j\in[1,n]$，在两棵树上 $\mathrm{LCA}(i,j)$ 的标号相同。
• 对于所有 $i,j$，在新树上 $\mathrm{LCA}(i,j)\le \max(i,j)+k$。

数据范围：$n\le 3\times 10^4,m\le 3000,k\le 10$。

思路分析

考虑 $k=0,m=1$ 如何做，不难发现第一个条件等价于 $1\sim n$ 的虚树不变，因此只需要在原树上插入一个点，可以插在边中间或者挂在节点下面，方案数 $2n-1$。

对于 $k=0$ 的一般情况，此时要求每个前缀的虚树都不包含更大的节点，从 $n+1\sim n+m$ 依次插入每个节点，方案数 $\prod_{i=n}^{n+m-1}(2i-1)$。

对于原问题，我们依然考虑依次插入 $i=n+1\sim n+m$，但是插入 $i$ 时 $i$ 可以不在 $1\sim i-1$ 的虚树上，而是通过一个 $\mathrm{LCA}$ 挂上去，而这个 $\mathrm{LCA}$ 一定在 $[i+1,i+k]$ 范围内。

因此对于每个 $i$，要么直接将插入树上，有 $2(i-1)-1$ 种方案，要么在 $[i+1,i+k]$ 中另选择一个节点插在某条边中间，然后把 $i$ 挂在该节点下面。

不难设计出一个 dp，$f_{i,s}$ 表示当前已经插入 $1\sim i$，$[i+1,i+k]$ 中已经被插入的元素是集合 $s$，转移时如果 $0\in s$ 就跳过，否则按上述过程转移，注意此时树的大小是 $i+|s|$。

时间复杂度：$\mathcal O(n+mk2^k)$。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD=1e9+7;
int n,m,k,f[1<<10],pc[1<<10];
ll g[1<<10];
void solve() {
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<n;++i) scanf("%*d");
	memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
	if(!k) {
		ll s=1;
		for(int i=n;i<n+m;++i) s=s*(2*i-1)%MOD;
		return printf("%lld\n",s),void();
	}
	for(int i=1;i<(1<<k);++i) pc[i]=pc[i>>1]+(i&1);
	f[0]=1;
	for(int i=n;i<n+m;++i) {
		for(int s=0;s<(1<<k);++s) {
			if(s&1) g[s>>1]+=f[s];
			else {
				int z=i+pc[s],t=s>>1;
				g[t]+=1ll*f[s]*(2*z-1);
				for(int j=0;j<k;++j) if(!(t>>j&1)) g[t|(1<<j)]+=1ll*f[s]*(z-1);
			}
		}
		for(int s=0;s<(1<<k);++s) f[s]=g[s]%MOD,g[s]=0;
	}
	printf("%d\n",f[0]);
}
signed main() {
	int c,T; scanf("%d%d",&c,&T);
	while(T--) solve();
	return 0;
}