【AGC005 F】Many Easy Problems

发布时间：2020-12-14 05:07:23 所属栏目：大数据来源：网络整理

导读：神他吗一天考一道码农题两道 FFT（其实还是我推式子一窍不通）题意给你一棵 (n) 个点的树，再给你一个常数 (k) 。设 (S) 为树上某些点的集合，定义 (f(S)) 为最小的包含 (S) 的连通子图的大

神他吗一天考一道码农题两道 FFT（其实还是我推式子一窍不通）

题意

　　给你一棵 (n) 个点的树，再给你一个常数 (k)。
　　设 (S) 为树上某些点的集合，定义 (f(S)) 为最小的包含 (S) 的连通子图的大小。
　　(n) 个点选 (k) 个点一共有 (tbinom{n}{k}) 种方案，请求出所有方案的 (f(S)) 之和。
　　出题人觉得这样就太简单了，他决定让你求出 (k=1cdots n) 的答案。
　　对于 (27%) 的数据，(nle 2700)
　　对于 (100%) 的数据，$ nle 2times 10^5$

题解

　　这种题的关键点在于 (n^2) (text{dp})。
　　首先无法对于每个 (k) 快速求出答案，但我们可以考虑一个点对每个 (k) 的贡献。

　　把 (x) 转为整棵树的根，则一个点 (x) 在这个连通子图内，当且仅当这 (k) 个点不都在 (x) 的某一个儿子子树里。　　那么贡献为 $

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!