考虑树的情况，自根向下确定颜色，根节点有 $k$ 种方案，每个非根结点都有个父亲，为了不与父亲同色，有 $k-1$ 种方案，故总染色方案数为 $k(k-1)^{n-1}$。

对于单个环。先断环为链，钦定第一个点染色为 $1$，那么求出方案数之后总方案数为其 $k$ 倍。记 $f_{a,b}$ 表示前 $a$ 个点染完，最后一个染色 $b$ 的方案数，转移为 $f_{i,j} \rightarrow f_{i+1,k}$，要求 $j\ne k$。复杂度 $O(n k)$。注意到 $f_{a,*}$ 中只包含两个值，即可以发现 $f_{a,1}= g_{a,0},f_{a,2}=\cdots=f_{a,k}=g_{a,1}$，所以直接对 $g$ dp 即可，转移 $g_{i,0}=(k-1)g_{i-1,1},g_{i,1}=g_{i-1,0}+(k-2)g_{i-1,1}$，长度为 $n$ 的链的方案数为 $h_n=(k-1)g_{n,1}$，再乘以 $k$ 得到总方案数。复杂度 $O(n)$。

对于仙人掌，把每个环缩为一个点之后变成一棵树。类似树的做法，自上而下确定颜色，对于根节点所代表的环，任意方案都可行，设其大小为 $s$，贡献为 $k h_s$；对于非根结点代表的环，环的顶端结点存在一个父亲不能同色，设其大小为 $t$，贡献为 $(k-1)h_t$。将贡献相乘得到总方案数。需要 Tarjan 求边双，复杂度 $O(n+m)$。