当前位置：首页 > news >正文

打卡信奥刷题（3341）用C++实现信奥题 P9414 「NnOI R1-T3」元组

news 2026/5/30 17:31:43

P9414 「NnOI R1-T3」元组

题目背景

小 L 很喜欢树，很喜欢 $ \operatorname{LCA} $，很喜欢有序元组，于是有了这样一道题。

题目描述

对于一棵 $ n $ 点有根树（根为 $ 1 $），定义有序 $ p $ 元组 $ (a_1,a_2,…,a_p) $ 为 $ k $ 级 $ \operatorname{LCA} $ $ p $ 元组当且仅当：

$ 1 \le a_1<a_2<…<a_p \le n $
存在 $ x $ 使得对于任意有序严格递增 $ k $ 元组 $ b \subseteq a $ 均满足 $ \operatorname{LCA}_{i=1}^{k}{b_i} = x $。

注意，$ \operatorname{LCA}(x,y) $ 指树上 $ x $ 点和 $ y $ 点的最近公共祖先，且 $ \operatorname{LCA}_{i=1}^{k}{b_i} $ 指的是所有的 $ b_i $ 的 $ \operatorname{LCA} $。

求出 $ k $ 级 $ \operatorname{LCA} $ $ p $ 元组的个数，对 $ 10^9+7 $ 取模。

输入格式

第一行一个整数 $ n,p,k $。

接下来 $ n-1 $ 行，每行两个整数代表一条边的两个端点的编号。

输出格式

输出一个整数代表要求的答案。

输入输出样例 #1

输入 #1

6 4 3 1 2 2 3 3 4 3 5 3 6

输出 #1

输入输出样例 #2

输入 #2

6 3 2 1 2 1 3 1 4 1 5 1 6

输出 #2

输入输出样例 #3

输入 #3

6 4 2 1 2 1 3 2 4 2 5 3 6

输出 #3

说明/提示

【样例 1 解释】

对于样例 $ 1 $，我们发现符合要求的 $ 4 $ 元组只有 $ (3,4,5,6) $。

【数据规模与约定】

对于 $ 100% $ 的数据，$ 2 \le n \le 5000，，，2 \le k \le p \le n $。

提示：本题开启捆绑测试。

Subtask 1（10 pts）：$ n \le 10 $。
Subtask 2（20 pts）：$ n \le 20 $。
Subtask 3（30 pts）：$ n \le 500 $。
Subtask 4（10 pts）：$ 1 $ 和所有点存在直接连边。
Subtask 5（30 pts）：无特殊限制。

【贡献名单】

data&check：EstasTonne。（主题库里这个题下一个题号的出题人）

C++实现

#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;constintN=5010,mod=1e9+7;intn,p,k;vector<int>e[N];intsz[N];intf[N][N];ll ans;voiddfs(intu,intfa){sz[u]=1,f[u][0]=f[u][1]=1;for(intj:e[u]){if(j==fa)continue;dfs(j,u);intpsz=sz[u];sz[u]+=sz[j];for(intd=min(sz[u],p);d>=1;d--)for(intt=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;}intmain(){scanf("%d%d%d",&n,&p,&k);for(inti=1;i<n;i++){inta,b;cin>>a>>b;e[a].push_back(b);e[b].push_back(a);}dfs(1,-1);cout<<ans<<endl;}