A：

首先计算出每个位置与它匹配的另一个位置，这一段区间为包含这两个位置的最小合法区间。

考虑拓展，递推预处理出在这个合法区间左侧和右侧紧挨着的合法区间数，这部分的方案数为 $(cnt_L+1)\times(cnt_R+1)$，然后还有可能被某个区间包含，在计算匹配位置的时候顺便计算包含这个合法区间的最小合法区间，加上这个区间的答案即可。

B：

8.30 的 A。

C：

首先我们不考虑 “两个矩阵如果删除的元素位置不同，但最后得到的结果相同，我们认为是相同的” 这句话，可以得到一个朴素的 dp：$f_{i,j}=\sum\limits_{j-k\leq l \leq j+k}f_{i-1,l}$，然后这个用前缀和优化转移即可做到 $\mathcal O(nm)$。

回过头来观察这句话对结果的影响，同一行一段相等的元素，移除它们的结果是一样的，这意味着我们会计算许多重复状态，考虑去除重复贡献。

我们发现对于第 $i$ 行相邻的两个相同元素 $j-1,j$，它们对应上一层的范围是这样的：

（红线为 $j-1$，蓝线为 $j$）

显然，上图中被白线框出来的线段被重复覆盖了，这一段为 $[j-k,j+k-1]$。

我们新增一个数组 $g$ 来记录每个元素可能会重复计算的贡献，那么 $f$ 的转移方程就不难推出：

$$f_{i,j}=\sum\limits_{j-k\leq l \leq j+k}f_{i-1,l}-\sum\limits_{j-k+1\leq l \leq j+k}g_{i-1,l}$$

注意 $g$ 的起始位置为 $j-k+1$，因为左端点不会产生重复贡献。

根据 $g$ 数组的定义和我们上面推出的式子，可以得到转移：

$$g_{i,j}=[a_{i,j}=a_{i,j-1}]\times (\sum\limits_{j-k\leq l\leq j+k-1}f_{i-1,l}-\sum\limits_{j-k+1\leq l\leq j+k-1}g_{i-1,l})$$

答案即为 $\sum\limits_{1\leq i\leq m} f_{n,i}-\sum\limits_{2\leq i\leq m} g_{n,i}$。

然后这个也是从一段区间转移，前缀和优化即可，时间复杂度 $\mathcal O(nm)$。

D：

对于树的部分，直接树剖线段树维护即可。

对于 50pts，首先把边排序，然后从小到大加边，当加入某条边时，如果还未加入的边中存在一条边使询问的点对所在连通块恰好联通，那么新加入的这条边即为所求。

然后还不会。