二项式反演的主要内容就是：
\[ f_n = \sum_{i = 0}^n (-1)^i {n \choose i} g_i \longleftrightarrow g_n = \sum_{i = 0}^n (-1)^i {n \choose i} f_i \]
这个反演的式子非常的优美：在这种形式下，它们是对称的。当然，亦可以写作：
\[ f_n = \sum_{i = 0}^n {n \choose i} g_i \longleftrightarrow g_n = \sum_{i = 0}^n (-1)^{n – i} {n \choose i} f_i \]
真的是玄妙重重。
我们先思考正常的暴力搜索：枚举每一次按下的颜色，然后检查继续更新。考虑用 IDA* 优化这个过程，首先估值函数就是剩下的颜色个数，因为至少需要更新这些颜色才有可能到达最终状态。然后注意控制 BFS 求连通块的个数的优化就行了。很好的一道题。
如果我们知道\(\{ f_n \}, \{ g_n \}\)有这种情况时：
\[ f_n = \sum_{i = 0}^n a_{ni} g_i \]
那么我们就可以用已知的\(f_0, f_1, \dots, f_n\)的值来求出\(g_n\)：
\[ g_n = \sum_{i = 0}^n b_{ni} f_i \]
上面这种求值方式叫做反演。
对于一个函数\(f(x)\)，如果该函数在其定义域上处处可导，则可以写成一个多项式函数（也就是这个函数的泰勒展开）。一般的，我们有：
\[ f(x) = \sum_{n = 0}^{\infty} \frac{f^{(n)}(x_0)}{n!}(x – x_0)^n \]
当\(x_0 = 0\)时，这个式子亦成为麦克劳林级数。
正常来讲，在矩阵树中，我们其实要算的东西就是这个：
\[ \sum_T \prod_{e \in T} p_e, \forall p_e = 1 \]
我们算的其实就是概率都为\(0/1\)的情况。现在我们要算：
\[ \sum_T \prod_{e \in T} p_e \prod_{e \notin T} (1-p_e) \]
我们可以考虑写成和式内仅与矩阵有关的式子：
\[ \sum_T \prod_{e \in T} p_e \frac{ \prod_e (1 – p_e) }{\prod_{e \in T} (1-p_e) } \]
合并积和式：
\[ \prod_e p_e \sum_T \prod_{e \in T} \frac{p_e}{1 – p_e} \]
然后我们把矩阵的内容改成\( \frac{p_e}{1 – p_e} \)就行了。
动态点分治真不友好。
我们先来考虑\(O(nq)\)的静态做法。我们可以随便定一个根，\(O(n)\)处理两个数组来记录子树的权值和与子树之外的权值和，然后再来一次\(O(n)\)判定答案是否最小。
其实从这个地方，我们可以发现一些关系：如果一个点的子节点比父节点更优，会有这样的关系：
\[ dist(fa[u], u) * (sum[fa[u]] – sum[u]) < dist(fa[u], u) * (sum[u]) \]
其中\(sum\)数组是子树的权值和。总结一下就是：
\[ 2 * sum[u] > sum[fa[u]] \]