自动搬运

查看原文

来自洛谷，原作者为

	Bulyly 09年在役选手

搬运于2025-08-24 22:48:09，当前版本为作者最后更新于2023-06-11 19:48:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 很合胃口的一道题。

• 考虑枚举每个点 $u$ 为 LCA 时对方案数产生的贡献。显然此时满足要求的点应该在 $u$ 的子树当中。将其子树中点对形成的 LCA 分为 $u$ 与非 $u$ 两类。

• 根据鸽巢原理可得，一个符合条件的 $p$ 元组应该最多只能出现 $k-1$ 个 LCA 为非 $u$ 类。于是问题转换为找非 $u$ 两类集合的数量。

• 更进一步，显然以子节点为根的树中任意点对才是非 $u$ 类的，所以一个子树中我们最多可选 $k-1$ 个。令 $f[u][t]$ 表示以 $u$ 为 LCA ,再子树中取 $t$ 个点的方案数。答案为 $f[u][p]$。用树上背包实现。

下附代码：

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=5010,mod=1e9+7;
int n,p,k;
vector<int> e[N];
int sz[N];
int f[N][N];
ll ans;

void dfs(int u,int fa) {
	sz[u]=1,f[u][0]=f[u][1]=1;
	for(int j:e[u]) {
		if(j==fa)  continue;
		dfs(j,u);
		int psz=sz[u];
		sz[u]+=sz[j];
		for(int d=min(sz[u],p);d>=1;d--)
			for(int t=max(1,d-psz);t<=min(min(k-1,d),sz[j]);t++)
				f[u][d]+=1ll*f[u][d-t]*f[j][t]%mod,
				f[u][d]%=mod;
	}
	ans+=f[u][p]; 
	ans%=mod;
}

int main() {
	
	scanf("%d%d%d",&n,&p,&k);
	for(int i=1;i<n;i++) {
		int a,b;
		cin>>a>>b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	dfs(1,-1);
	cout<<ans<<endl;
}

完结撒花~