首先根据猜结论数学归纳法可以想到在\(k\)为奇数时答案依然是\(1\)
因此我们只考虑\(k\)是偶数的情况
方法1：
容易想到好点相当于这棵树上只考虑\(k\)个关键点的中心
则显然根据重心定义，我们枚举每个点为重心的情况，则对于他的每个儿子，我们可以用dp或者容斥原理来从中选出\(\leq \frac{k}{2}\)个点，这里重点说一下容斥原理
因为发现对于每个儿子最多有一个儿子内选的点的个数\(> \frac{k}{2}\)，因此我们枚举是哪个儿子的子树选了这么多的点，可以得到答案\(\sum\limits_{(u,v) \in E}{\sum\limits_{i=\frac{k}{2}+1}^{k}{\binom{siz_v}{i} \binom{n-siz_v}{k-i}}}\)
这样我们就可以得到一个\(O(n^2)\)的做法，但这个做法显然不够优秀
我们考虑优化一下做法，显然\(dp\)是没法再优化的，因此我们考虑优化容斥
设\(f_x=\sum\limits_{i=\frac{k}{2}+1}^{k}{\binom{x}{i} \binom{n-x}{k-i}}\)
观察\(f_x\)的组合意义，我们发现\(f_{x+1}\)相对与\(f_x\)多的部分实际上就是前\(x\)个数恰好选了\(i+1\)个，和前\(x\)个数选\(i\)个第\(x+1\)个数必须选的情况
因此可以得到\(f_{x+1} = f_x + \binom{x}{\frac{k}{2}} \binom{n-x-1}{k-\frac{k}{2}-1}\)
于是我们可以实现\(O(n)\)预处理\(O(n)\)计算，总复杂度\(O(n)\)
方法2：
首先可以证明好点一定对应树上的一个连通块，根据重心的定义，这是显然的(其实限制更严格，答案在树上是一条链，但这里不需要这么严格的限制)
我们考虑计算树上的点并不好算，但如果对于一条边\((u,v) \in E\)中\(u\)和\(v\)都是好点，则把边\((u,v)\)切开分成的两棵树中关键点的个数显然是一样的
而且由于答案在树上是一个联通快，我们可以通过联通块内边的个数+1得到联通快内点的个数
因此我们对于每条边考虑他左右两边各选\(\frac{k}{2}\)的方案数，答案即为：
\[\sum\limits_{(u,v)\in E}{\binom{siz_u}{\frac{k}{2}}\binom{n-siz_u}{\frac{k}{2}}} \]同样可以做到\(O(n)\)
标签：frac,limits,siz,sum,个数,CF1824B2,binom From： https://www.cnblogs.com/fox-konata/p/17656022.html