可能更好的阅读体验
好题。碍于场上策略原因没有场切这个题，但也算是单杀了，来写篇题解。
首先这个平方和就很可以拆，直接变成选两条长度为 l 的链，在任意一条链上的点颜色均相同，其它点颜色任意的方案数。
这个东西就可以直接 DP 了，可以直接导出一个 O(n^3l^2) 的做法，具体地，设 f_{u, v, x, y} 表示两条链走到 u, v，长度分别为 x, y 的方案数，每次转移拓扑序更小的点并处理 u = v 的情况即可。
但是这个做法并没有什么优化空间，又因为题目中 n 比 l 更大，所以我们更倾向于一个 O(n^2poly(l)) 的做法。发现记录两个点是没有必要的，只需要记录它们重合的位置。即，设 f_{u, x, y} 表示两条链最后一次重合在 u，长度分别为 x, y 的方案数，每次转移时枚举下一个重合的位置。但是这样转移的系数是不好算的。
那么我们放弃钦定它们在途中不重合，改为钦定它们重合的次数，最后用二项式反演得出恰好重合这么多次的答案。具体来说，设 f_{u, x, y, i} 表示两条链最后一次重合在 u，长度分别为 x, y，钦定重合了 i 次的方案数，g_{u, v, i} 表示 u 走到 v 恰好走 i 条边的方案数，那么有转移方程：
f_{u, x, y, i} \times g_{u, v, p} \times g_{u, v, q} \to f_{v, x + p, y + q, i + 1}
然后设 h1_i 为钦定重合了 i 次的总方案数，h2_i 为恰好重合了 i 次的总方案数，有：
h2_i = h1_i - \sum_{j = i + 1}^l \binom ji h2_j\\
ans = \sum_{i = 0}^l k^{n - 2l + i + 1} h2_i
直接转移即可做到 O(n^2l^5)。发现转移是一个二维卷积，但可以变成两次一维卷积，可以优化到 O(n^2l^4)，然后就可以获得 84 了。考虑那个 i 维与转移无关，尝试优化。
我们考虑另一种二项式反演：
h2_i = \sum_{j = i}^l \binom ji (-1)^{j - i} h1_j\\
\begin{aligned}
ans &= \sum_{i = 0}^l k^{n - 2l + i + 1} h2_i\\
ans &= \sum_{i = 0}^l k^{n - 2l + i + 1} \sum_{j = i}^l \binom ji (-1)^{j - i} h1_j\\
&= k^{n - 2l + 1} \sum_{j = 0}^l h1_j \sum_{i = 0}^j k^i (-1)^{j - i}\binom ji\\
&= k^{n - 2l + 1} \sum_{j = 0}^l h1_j (k - 1)^j\\
\end{aligned}
那么我们在转移过程中将系数乘上去即可，这样就省掉了 i 维。时间复杂度为 O(n^3l + n^2l^3)。