CodeCraft-22 and Codeforces Round 795

發表於 2022-06-04 更新於 2024-10-23 分類於 Codeforces ， Div2 Disqus：文章字數： 271 所需閱讀時間 ≈ 1 分鐘

F(贡献统计,组合数,树)

题目

树,n个点,点上1~n

给定k

对于点r, 树的一个k个点的子点集S, 令f(r,S) = 根为r, 且包含所有S中点的原树的子树最少的点的个数

你需要计算所有 r和S的组合求所有f(r,S)的和

答案mod 1e9+7

n 2e5

512MB

看数据范围n方都不行, 既然又是求和

那么估计又是算贡献一类

从树的结构讲, 与其算贡献不如算不被贡献

一个点u,连接了很多点v0,v1,v2,v3

如果要u不被贡献, 那么r和S的所有点一定在某个vi的联通块内,不会是不同vi的联通块内

而选择来讲, 对于S, 就是C(联通块大小,k), 对于r就是联通块大小

注意联通块 < k时方案为0

感觉就过了???不想写代码

鸽

感觉给时间, 就这样随便搞一搞就完了?

无