这次因为Windows和Linux换行符不同，
T2getchar挂了60分，
CSP-S最好还是不要用
标签：
状压Dp
题解：
考虑对点的奇偶性做状压:dp[i][j]代表第i层状态为j的方案数，转移分为取反和不取反
但是这样做复杂度是1e9，需要把边也状压起来，并预处理出每个状态的1的个数
这样便可以做到O(1)求出某一状态下某点的奇偶性，复杂度少一个k，足以通过本题
标签：
随机化
题解：
设g[i]代表包含i的集合个数，由期望的可加性，任意两个集合的交的期望为
$E=\sum\limits_{i=1}^{n*2}\frac{C(g[i],2)}{C(n+1,2)}$
当g[i]平均分配时g[i]会取到最小值，charm说是因为组合数的增长速度很快
则最坏情况下$ E=\frac{n-1}{2} $，直接随机化n对即可?我在问charm
标签：
贪心
题解：
考场上打了k=1和s=1的部分分以及一个假贪心，结果和直接输出n除s向上取整一个分?!
正解是贪心：
设f[i][j]代表第i个点的子树中深度为j的可分配个数
g[i][j]代表第i个点的子树中深度为j的需求个数
每次只为深度为k的需求新增灭火器，之后考虑灭火器与需求的结合:
不难想到结合只发生在lca处，所以对于每个点贪心的按照深度从大到小去尽量满足需求，
root处把所有的需求全部收割掉即可
原文：https://www.cnblogs.com/AthosD/p/11832934.html