P9414 「NnOI R1-T3」元组题目背景小 L 很喜欢树很喜欢 $ \operatorname{LCA} $很喜欢有序元组于是有了这样一道题。题目描述对于一棵 $ n $ 点有根树根为 $ 1 $定义有序 $ p $ 元组 $ (a_1,a_2,…,a_p) $ 为 $ k $ 级 $ \operatorname{LCA} $ $ p $ 元组当且仅当$ 1 \le a_1a_2…a_p \le n $存在 $ x $ 使得对于任意有序严格递增 $ k $ 元组 $ b \subseteq a $ 均满足 $ \operatorname{LCA}_{i1}^{k}{b_i} x $。注意$ \operatorname{LCA}(x,y) $ 指树上 $ x $ 点和 $ y $ 点的最近公共祖先且 $ \operatorname{LCA}_{i1}^{k}{b_i} $ 指的是所有的 $ b_i $ 的 $ \operatorname{LCA} $。求出 $ k $ 级 $ \operatorname{LCA} $ $ p $ 元组的个数对 $ 10^97 $ 取模。输入格式第一行一个整数 $ n,p,k $。接下来 $ n-1 $ 行每行两个整数代表一条边的两个端点的编号。输出格式输出一个整数代表要求的答案。输入输出样例 #1输入 #16 4 3 1 2 2 3 3 4 3 5 3 6输出 #11输入输出样例 #2输入 #26 3 2 1 2 1 3 1 4 1 5 1 6输出 #220输入输出样例 #3输入 #36 4 2 1 2 1 3 2 4 2 5 3 6输出 #30说明/提示【样例 1 解释】对于样例 $ 1 $我们发现符合要求的 $ 4 $ 元组只有 $ (3,4,5,6) $。【数据规模与约定】对于 $ 100% $ 的数据$ 2 \le n \le 5000 2 \le k \le p \le n $。提示本题开启捆绑测试。Subtask 110 pts$ n \le 10 $。Subtask 220 pts$ n \le 20 $。Subtask 330 pts$ n \le 500 $。Subtask 410 pts$ 1 $ 和所有点存在直接连边。Subtask 530 pts无特殊限制。【贡献名单】datacheckEstasTonne。主题库里这个题下一个题号的出题人C实现#includebits/stdc.husingnamespacestd;usinglllonglong;constintN5010,mod1e97;intn,p,k;vectorinte[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(jfa)continue;dfs(j,u);intpszsz[u];sz[u]sz[j];for(intdmin(sz[u],p);d1;d--)for(inttmax(1,d-psz);tmin(min(k-1,d),sz[j]);t)f[u][d]1ll*f[u][d-t]*f[j][t]%mod,f[u][d]%mod;}ansf[u][p];ans%mod;}intmain(){scanf(%d%d%d,n,p,k);for(inti1;in;i){inta,b;cinab;e[a].push_back(b);e[b].push_back(a);}dfs(1,-1);coutansendl;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
打卡信奥刷题（3341）用C++实现信奥题 P9414 「NnOI R1-T3」元组
P9414 「NnOI R1-T3」元组题目背景小 L 很喜欢树很喜欢 $ \operatorname{LCA} $很喜欢有序元组于是有了这样一道题。题目描述对于一棵 $ n $ 点有根树根为 $ 1 $定义有序 $ p $ 元组 $ (a_1,a_2,…,a_p) $ 为 $ k $ 级 $ \operatorname{LCA} $ $ p $ 元组当且仅当$ 1 \le a_1a_2…a_p \le n $存在 $ x $ 使得对于任意有序严格递增 $ k $ 元组 $ b \subseteq a $ 均满足 $ \operatorname{LCA}_{i1}^{k}{b_i} x $。注意$ \operatorname{LCA}(x,y) $ 指树上 $ x $ 点和 $ y $ 点的最近公共祖先且 $ \operatorname{LCA}_{i1}^{k}{b_i} $ 指的是所有的 $ b_i $ 的 $ \operatorname{LCA} $。求出 $ k $ 级 $ \operatorname{LCA} $ $ p $ 元组的个数对 $ 10^97 $ 取模。输入格式第一行一个整数 $ n,p,k $。接下来 $ n-1 $ 行每行两个整数代表一条边的两个端点的编号。输出格式输出一个整数代表要求的答案。输入输出样例 #1输入 #16 4 3 1 2 2 3 3 4 3 5 3 6输出 #11输入输出样例 #2输入 #26 3 2 1 2 1 3 1 4 1 5 1 6输出 #220输入输出样例 #3输入 #36 4 2 1 2 1 3 2 4 2 5 3 6输出 #30说明/提示【样例 1 解释】对于样例 $ 1 $我们发现符合要求的 $ 4 $ 元组只有 $ (3,4,5,6) $。【数据规模与约定】对于 $ 100% $ 的数据$ 2 \le n \le 5000 2 \le k \le p \le n $。提示本题开启捆绑测试。Subtask 110 pts$ n \le 10 $。Subtask 220 pts$ n \le 20 $。Subtask 330 pts$ n \le 500 $。Subtask 410 pts$ 1 $ 和所有点存在直接连边。Subtask 530 pts无特殊限制。【贡献名单】datacheckEstasTonne。主题库里这个题下一个题号的出题人C实现#includebits/stdc.husingnamespacestd;usinglllonglong;constintN5010,mod1e97;intn,p,k;vectorinte[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(jfa)continue;dfs(j,u);intpszsz[u];sz[u]sz[j];for(intdmin(sz[u],p);d1;d--)for(inttmax(1,d-psz);tmin(min(k-1,d),sz[j]);t)f[u][d]1ll*f[u][d-t]*f[j][t]%mod,f[u][d]%mod;}ansf[u][p];ans%mod;}intmain(){scanf(%d%d%d,n,p,k);for(inti1;in;i){inta,b;cinab;e[a].push_back(b);e[b].push_back(a);}dfs(1,-1);coutansendl;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
