不妨先从简单的图结构开始做。

链是容易的。第一个节点任意放，方案数为 $k$；后面的节点不能和前一个节点颜色相同。均为 $k-1$。由乘法原理，$n$ 个节点的链方案数为 $k(k-1)^{n-1}$。

然后考虑树。除去根，每个节点最多只有一个父亲，所以方案数是一样的。

然后考虑环。环就是链上多加了一条边。那么最后一个点和第一的点的颜色也不能一样。直接做好像不好做。考虑容斥。先算出总方案数，也就是链的方案数，然后减去第一个点和最后一个点颜色一样的方案数。那不妨把这两个点看作一个整体缩为一个点。我们发现它就是少了一个点的环！也就是说，$n$ 个点的环染色方案数等于 $n$ 个点链染色方案数减去 $n-1$ 个点环染色方案数。因此我们就可以递推出 $n$ 个点环染色的方案数。

接下来是仙人掌。我们不妨来考虑树边对环的影响。环直接全乘起来即可。那树边呢？不妨钦定连了树边的点是第一个点，那么就是 $k$ 种染发变成了 $k-1$ 种，因为树边让它少掉了一种能染的颜色。因此树边的贡献为 $\dfrac{k-1}{k}$。

设所有环的方案数之积为 $c$，树边数量为 $t$，方案数即为 $c\dfrac{(k-1)^t}{k^t}$。

因此只要跑出所有边双连通分量，将环先算出来，然后算出树边数量（可以总边数减去环上边数），就可以求出答案。