对n个连续方格进行m着色使得相邻颜色有相同的方案总数
比较简单的想法是用总数减不合法
总数：$m^n$
不合法个数：第一个有$m$种选择，之后每个都不能和前面一样，所以是$m(m-1)^{n-1}$种
$ans=m^n-m(m-1)^{n-1}$
结论：一行n个方格进行m着色使得有相邻两个颜色相同的方案数为$m^n-m(m-1)^{n-1}$
经验：①总体减空白等于阴影 ②直接从每一个元素上面入手
一棵树的$n$个节点放在一个环上，求使得边不交叉的方案总数
先无根树转成有根树（根为$1$），然后可以得出一棵子树在圆上一定是连续的。
在子树内部如何乱排几个儿子都是可以的，所以$i$的贡献是$d_i$即i的度数
结论：一棵树的$n$个节点放在一个环上，边不交叉的方案为$pai(d_i)$
经验：①无根树转有根树 ②敢于猜测结论 ③统计每个单位的贡献较为方便
原文：https://www.cnblogs.com/hojqvfna-tcl/p/11156812.html