「NnOI R1-T3」元组

Bulyly · 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;
}

完结撒花~