P4821 [中山市选] 生成树

· · 题解

生成树无环。考虑删边破环。

图中有 1 个 n 边形以及 n 个 5 边形。

首先删去中间的 n 边形中的一条边，共有 n 种删法。

观察剩余的图形，为 (n-1) 个完整的 5 边形与 1 个少一条边的 5 边形。对于每个完整的 5 边形，有 5 种删法；对于少一条边的 5 边形，有 4 种删法。

因此答案为 n\times 5^{n-1}\times 4。

Submission。