自动搬运

查看原文

来自洛谷，原作者为

	MaiJingYao666 格兰蚊多

搬运于2025-08-24 23:02:28，当前版本为作者最后更新于2025-08-18 16:52:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P10912 [蓝桥杯 2024 国 B] 数星星 题解

解题思路

首先，题目的意思就是数菊花图。

记一个节点的子节点个数为 $s_i$。

我们对于一个菊花，考虑它在树中的构造。显然如果已经确立了菊花的“根”，那么剩下的“花瓣”就一定是它的子节点或父节点。

那么对“花瓣”中有无父节点进行讨论，假设要选 $x$ 个点：

1. 有父节点。前置条件是至少也要选一个子节点，不然会有重复。那么个数就是 $C_{s_i}^{x-2}$。
2. 无父节点。个数显然是 $C_{s_i}^{x-1}$。

显然一个点只会作为子节点一次，所以大力枚举即可。

组合数的话，模数是质数，预处理阶乘再用费马小定理即可。

AC 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int N=1e5+50;
int n,l,r;
vector<int> G[N];
int siz[N];
void dfs(int p){
	for(auto j:G[p]){
		if(siz[j]) continue;
		siz[p]++;
		dfs(j);
	}
}
ll qpow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return res;
}
ll jc[N];
ll C(int a,int b){
	if(b>a) return 0LL;
	return jc[a]*qpow(jc[a-b],mod-2)%mod*qpow(jc[b],mod-2)%mod;
}
int main(){
	scanf("%d",&n);
	jc[0]=jc[1]=1LL;
	for(ll i=2;i<=n;i++){
		jc[i]=jc[i-1]*i%mod;
	}
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1);
	scanf("%d%d",&l,&r);
	ll ans=0;
	for(int j=l-1;j<=min(r-1,siz[1]);j++){
		ans=(ans+C(siz[1],j))%mod;
	}
	for(int i=2;i<=n;i++){
		for(int j=l-1;j<=min(r-1,siz[i]+1);j++){
			if(j>=2) ans=(ans+C(siz[i],j-1))%mod;
			if(j<=siz[i]) ans=(ans+C(siz[i],j))%mod;
		}
	}
	printf("%lld",ans);
}
/*

*/