apple

Link

考试的时候连看都没看的题目。。Orz ShallWe A掉此题。。

研究题解，还把题目都看错了，怎么都搞不懂。纸张。

Solution

要求选出一些点让它们变得无用，使得剩下的点的权值和$\le limit$。

可以枚举让哪些点变得无用从而使得权值和符合要求。$n\le 40$，而不同的点的枚举互相独立，可以用meet in the middle。剩下的只需要计算“让一些点变得无用”的方案数目。

让一些点变得无用，也就是钦定这些点必须连-1的点。$f[i]$表示钦定只有$i$个点无用的方案数，不好算，考虑容斥。$g[i]$表示钦定至少$i$个点无用的方案数。那么$f[i]=\sum\limits_{j=i}^n(-1)^{i-j}g[j]$。

那么$g[i]$怎么算？钦定至少$i$个点无用的操作相当于限定了$i$个点的连边，而剩下的点可以随便连。这个用Matrix-Tree就可以算出了。

Tips

一定要看对题目。。看不对题目的话，思考或者看题解都是浪费时间！！

Code