A. coin
首先可以猜出来每种钞票的贡献是独立的，所以只要对于每种钞票算出来贡献最后合并就行了。
直接做复杂度会死掉。
考虑对于每种钞票，张数随贡献的差分数组显然是单调的，所以可以用堆动态维护当前的最优解。
发现最多只会用到$n$种状态，所以动态的计算这些状态，而不必全部预处理出来。
B. B
我的做法是，求出来至少有k条边与原来的树相同的方案数，容斥就可以得到恰好的方案数。
方案数可以通过树形dp来求，设$f[i][j][k]$表示$i$的子树中选了$j$条边，$i$所在的连通块大小为$k$的方案数。
然后用数树中的那个式子就可以求出来方案数。
然后这个东西可以继续优化。考虑那个式子的实际含义，实际上就是在每个联通块内选出一个点的方案数。那么继续优化可以将第三维变成$0/1$，表示当前联通块是否已经选了。
这样的复杂度是$O(n^2)$的。
然后题解的做法是个套路，就是变元矩阵树+高斯消元，代入若干值直接搞即可。之前做过很多遍了。
C. battery
可以发现对于每个点的限制形如对若干点的同时不选的限制，似乎不可做，然而可以发现，假如在同一方向上同时出现两种炮台可以经过这个点，那么这两个炮台一定撞了。
所以经过一个点的炮台最多两个，并且来自不同方向，否则无解，那么就变成了限制两个不能同时不选的东西。
于是就是简单的2-sat模型，直接套就行了。