一眼可以了解到是一道割点题。对于不是割点的情况，那么被计算的点对一定包含此点本身，又因为有序，所以贡献就是\(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)) \]
这道题比较傻逼。
考虑记录上一个最近的\(1\)的位置\(nxt_i\)，然后显然的是：如果在\( O(n \log n) \)时间的扫描中扫描到\([l, r]\)大于当前区间，那么就考虑\(l\)左边是否有足够的零来补足长度。然后这道题就可以愉快的 AC 了。
考虑超级暴力，设计状态\(dp[k][i][j]\)为走了\(k\)步处于\((i, j)\)的答案：
\[ dp[k][i][j] = mp[i][j] + \max \begin{cases} dp[k – 1][i – 1][j] \\ dp[k – 1][i + 1][j] \\ dp[k – 1][i][j + 1] \\ dp[k – 1][i][j – 1] \end{cases} \]
这道题真的是令人窒息，也告诉了我比赛的时候上 QQ 是一个非常坏的习惯。
这道题 60 分做法非常之显然：相同体积的物品归为一种物品，且价值为同体积内最大的价值。这样就可以把物品数量压到 100 个以内。
但是这样是通过不了全部分数的，而且全部分数的容量非常之大，所以正常的 DP 优化是行不通的。做完上面的压缩之后，可以考虑做一些贪心进行优化。接下来我会详细的介绍这个贪心策略：
这道题的式子跟 Codeforces 一道 F 题是一样的，让我误以为是 BSGS 之类的玩意，最后发现其实算是矩阵乘法的题。
考虑任意一个答案都是由\(\{f_n\}\)的幂的积组成的，由于\(k\)很小，所以我们可以考虑计算每一个\(f\)的指数，然后就可以用快速幂来计算这些东西。