题解：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 细节的处理。