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

· · 题解

前置知识：组合数 、逆元 。不会的出门右转。

Part 1. 题意

给定一棵树，定义树上的一个子图 G 是一颗星星，当且仅当：

求这棵树不同的星星个数，对 10^9+7 取模。

Part 2. 分析

一个星星的本质，就是有且仅有两层的树。
设某个星星的节点数为 K，根节点的度数为 D，显然叶节点的选取方式有 \dbinom{D}{K-1} 种，分别枚举 K 和根节点，累加即可。要注意特判 K=1 时，总的方案数是 N；K=2 时，总的方案数要除以 2，因为此时无法区分根节点，会算重复。组合数的计算可以通过预处理阶乘和阶乘逆元实现。
分析一下时间复杂度。令节点 i 的度数为 D_i，那么 K 的枚举范围在 L-1 与 \min(D_i,R-1) 之间（含）。由于给定的图是树，那么 \sum_{D} = 2 N。易得 T(N) \le 2N。时间复杂度 \Theta(N)。

Part 3. AC Code

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=1e5;
const ll mod=1e9+7;

bool __stb;

int n,l,r;
int deg[N+1];
ll frc[N+1],inv[N+1],finv[N+1];
ll ans;

bool __enb;

ll qpow(ll a,ll b) {
    if(b==1) return a;
    ll t=qpow(a,b/2);
    if(b%2==0) return t*t%mod;
    return t*t%mod*a%mod;
}

void init() {
    frc[0]=1;
    for(int i=1;i<=n;i++) frc[i]=frc[i-1]*i%mod;
    inv[0]=1;
    for(int i=1;i<=n;i++) inv[i]=qpow(i,mod-2);
    finv[0]=1;
    for(int i=1;i<=n;i++) finv[i]=finv[i-1]*inv[i]%mod;
}

ll C(int x,int y) {
    if(x<0||y<0||x<y) return 0;
    return frc[x]*finv[y]%mod*finv[x-y]%mod;
}

int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cerr<<(&__enb-&__stb)/1024.0/1024.0<<" MB"<<endl;
    cin>>n;
    for(int i=1,u,v;i<n;i++) {
        cin>>u>>v;
        deg[u]++;
        deg[v]++;
    }
    cin>>l>>r;
    init();
    if(l==1) ans+=n,l++;
    if(l==2&&l<=r) {
        ll t=0;
        for(int i=1;i<=n;i++) (t+=deg[i])%=mod;
        ans+=t/2;
        l++;
    }
    if(l<=r) for(int i=1;i<=n;i++) {
        for(int j=l-1;j<=min(deg[i],r-1);j++) {
            (ans+=C(deg[i],j))%=mod;
        }
    }
    cout<<ans;
    return 0;
}