我们发现只需要保证在任何时候\(0\)的个数都大于等于颜色的数量。直接考虑一个一个塞球，不仅要考虑同质问题，还要考虑具体的颜色排列非常麻烦，不如我们一次性把所有的球都在序列上放好：设置\(dp[i][j]\)为\(i\)个\(0\)、\(j\)种颜色的局面，我们可以这样转移：
\[ dp[i][j] = dp[i – 1][j] + {n – i + (n – j + 1) \times (k – 2) – 1 \choose k – 2 } dp[i][j – 1] (n – j + 1) \]
解释一下：我们固定住该颜色的球的位置为最左能放置的点，然后乘上\(n – j + 1\)进行染色，并给剩余的\(k-2\)个球选位置。
也是比较巧妙的一个转换思想。
我们考虑列式：
\[ \sum_{i = 1}^n \sum_{j = i + 1}^n {a_i + b_i + a_j + b_j \choose a_i + b_i} \]
直接去算或者是按贡献计算都不行，我们考虑转换成这样：
\[ \frac{ \sum_{i = 1}^n \sum_{j = 1}^n {a_i + b_i + a_j + b_j \choose a_i + b_i} – \sum_{i = 1}^n {2(a_i + b_i) \choose a_i + b_i} }{2} \]
前面那个部分我们可以把点\((-a_i, -b_i)\)放在平面上，然后算一个路径计数的 DP 即可（因为平面大小比较小）。前半部分就是所有第三象限的点走到\((x_i, y_i)\)的路径总数，后半部分直接暴力算即可。
首先仔细剖析出题目意思：我们要规定一个路径，要被经过\(k\)，然后再到路径的两头延伸出不大于 \(k\) 的分支，且每个分支独占一颗子树，求方案数。
那么我们可以先把 \(1\) 定为根，然后算出以点 \(u\) 为端点、分支在子树内的方案数 \(f_u\)，然后再算向父亲侧的方案数 \(g_u\)，再枚举 \((u, v)\)：
首先需要知道一个性质：如果第一行和第一列确定，那么这个方案就已经完全确定了。这个可以用归纳法证明：
证明 如果格子\((i – 1, j)\)、\((i, j – 1)\)和\((i – 1, j – 1)\)的颜色确定，那么显然\((i, j)\)的颜色就能被唯一确定。如果第一行和第一列可以被确定，那么根据上述描述，便可生成一个唯一的方案。
所以欲记录方案的个数，那么就要记录合法的第一行和第一列的方案数。这样我们把问题转换到了长条上。
设置\(dp[i][0/1][0/1]\)为到第\(i\)位是否连续、最后一位填的数字。那么转移非常自然，可以自行推导（确实啊）。
最后答案就是把所有情况加起来，再减去非法的两种情况（也就是左上角的三格同色的情况）。
一眼可以了解到是一道割点题。对于不是割点的情况，那么被计算的点对一定包含此点本身，又因为有序，所以贡献就是\(2(n – 1)\)。如果是割点的话，就比较麻烦，分下面几个来算：
第一个很好算，是\(2(n – 1)\)。第二个，在 Tarjan 枚举搜索子树的时候计算子树大小和全图补集的乘积（注意，这里会多计算一遍与点\(u\)的点对，所以我们第一个改成算\(n – 1\)）；第三个，算「当前整颗搜索树与图的补集大小」与「搜索树的大小」的乘积。
综合起来就是，对于点\(u\)：
\[ ans_u = \sum_{k \in son(u)} (n – size(k)) \times size(k) + (n – 1) + (n – 1 – \sum_{k \in son(u)} size(k)) \times (1 + \sum_{k \in son(u)} size(k)) \]
看一眼复杂度，\(O(nm)\)级别的，考虑两个循环的 DP。分析整个题面之后发现，我们穿过边界时，当且仅当另一个连通块的权值比当前的大，否则便不会为了穿过边界而损失当前金块。所以，我们做一个 DP 一样的东西：因为发现每个格子只能走一遍，那么在每一列你只能选择一直向上走和一直向下走，所以这个 DP 便没了后效性，然后再处理连通块之间的连接判断就做完了。