题解：P5291 [十二省联考 2019] 希望

· · 题解

dp 的部分其它题解说得很详细了，重点说一下容斥的想法，即使想不到这个简洁明了的点减边也可以较为容易地推出该结论。

考虑一个集合点 u 合法的方案数，这要求每个连通块内的点到 u 的距离不超过 L。有 dp_{u,i} 表示 u 子树内部包含 u 的连通块，所有点到 u 的距离不超过 i 的方案数。可以长剖+换根解决一个点的问题，但是会算重。

子集容斥，考察一个集合合法的方案数。大概是对于这个集合的虚树，然后把叶子的子树部分与根外面的部分乘起来。这个方向感觉很没有前途，可以放弃把这玩意儿放到树上 dp 的想法。但是这也启发一个性质：如果一个集合合法，它们的斯坦纳树也是合法的，所以只需要对所有树上连通块进行容斥。

计数对象转变为树上连通块，那么先算一下容斥系数，考虑所有以其为斯坦纳树的集合 S 的 (-1)^{|S|-1} 之和。一个连通块对应到 2^c 个集合，其中 c 是该连通块的非叶节点个数。可以发现大多数情况下，一个连通块对应到偶数个集合，而且系数恰好抵消为 0。当且仅当该连通块 c=0，也就是该连通块全都是叶子的时候才会有系数。而连通块内的点全都是叶子（度数 \leq 1）只有一条边和一个点两种情况。其中一条边的系数是 -1，点的系数是 1。这样就得到了本题的 key observation。

点的情况第一段已经讨论过了。边的情况不像第二段说的对一个集合计数那么复杂，和点的情况十分类似。本题真正的毒点还是 dp 细节的处理。