正常来讲，在矩阵树中，我们其实要算的东西就是这个：
\[ \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]] \]
这道题是一道很考察思维的题目，我在这里介绍 DP 的做法。
我们考虑 DP。大概的方程可以写成：
\[ dp[i] = max\{ dp[j], j \in S_i \} + 1 \]
其中，\(dp[i]\)代表\([1, i]\)之间最多的斑点奶牛数量，然后\(S_i\)就是我们可以转移来的区间。我们可以提前处理好每一个点对应的\(lft_{S_i}, rig_{S_i}\)，也就是每一个点集合的左右端点。这个区间满足一个根本的条件：这个区间是点\(i\)左边最近的、不包含\(i\)的集合。我们肯定可以从这一段区间搞出最大的答案。预处理的时候先默认\(rgt[i] = i – 1\)，最后做个小 DP 更新数据即可。
注意：这道题在 BZOJ 上是权限题，我是在 JZOJ 上做的。
刚刚解决完电力网络的问题，阿狸又被领导的任务给难住了。
刚才说过, 阿狸的国家有\(n\)个城市，现在国家需要在某些城市对之间建立一些贸易路线, 使得整个国家的任意两个城市都直接或间接的连通。
为了省钱，每两个城市之间最多只能有一条直接的贸易路径。对于两个建立路线的方案, 如果存在一个城市对，在两个方案中是否建立路线不一样，那么这两个方案就是不同的，否则就是相同的。现在你需要求出一共有多少不同的方案。
好了，这就是困扰阿狸的问题。换句话说，你需要求出\(n\)个点的简单（无重边无自环）无向连通图数目。
由于这个数字可能非常大，你只需要输出方案数 mod 1004535809(479 * 2 ^21 + 1) 即可。
FFT、NTT、多项式乘法。
现在我们有一个这样的式子：
\[ A(x)B(x) \equiv C(x) \ (mod \ x^n) \]
现在我们已知\(B(x), C(x)\)的信息，而我们计算答案的时候需要用\(A(x)\)进行运算。这个时候，我们需要求出\(B(x)\)的逆元。多项式求逆元，我们一般是用倍增的方式来求解。假如我们有\(B(x)\)在模\(x^{\lceil \frac{x}{2} \rceil}\)意义下的逆元\(D(x)\)：