思路

看到有 个障碍点并且障碍点非常少，所以想到暴力容斥，用总方案减去不合法的方案数。

只要经过任意一个障碍点，就是一个不合法方案。所以令 表示只经过障碍点 的方案数。

P8010 「Wdsr-3」令人感伤的红雨

提供一个 的卡常做法。

思路

对于 的情况，加上一条边时，树上出现了一条环且长为 ，环上的原路径都可以少走一遍，再算上新路径要走一遍。此时答案为 。
我们需要令 尽可能大，即原路径的那条链尽可能长，那么应该取树的直径。