省流：被诈骗的一集

T1

诈骗题。

本题的性质只能从答案入手，很难观察到答案不超过 $3$ ，具体的就是令 $i=n-2,j=n-1$ 。那么由于 LCP 肯定不超过长度，所以答案构造 $\le 3$ 。

一个暴力的想法就是暴力枚举两个指针 $i,j$ 来去判断，但是这是 $O(n^2)$ 的，不过有了答案 $\le 3$ 我们思考具体取值。

考虑固定 $i$ 。首先 $j\in[i+1,i+3]$ 的枚举是肯定需要的，复杂度可以接受。但是一但到了 $i+4$ 之后呢？结论是直接取到 $j=n-1$ 即可，答案还是因为答案不超过 3，可以让 $LCP(a,c)+LCP(b,c)=0$ 当且仅当存在 $c_j\neq a_1\land c_j\neq b_i$ 。否则：如果 $a_1\neq b_i$ ，我们选 $j = n - 1$ 就有 $LCP(a,c)+LCP(b,c)=1$ ，最优；如果 $a_1 = b_i$ ，那后面的 $c_j$ 也都和它们相等， $LCP(a,c)+LCP(b,c)\ge 2$ ，还是选 $j=n-1$ 最优。

所以就枚举 $i$ ，然后按照上面暴力统计即可。

总结：当且仅当无法从正向导出任何有效结论且用时过长，考虑从答案入手。一个简要的方法就是通过暴力或题目所给出的特殊性结构（例如树），通常会发现答案与给出的特殊性结构或着取值在一个范围内。

T2

题意就是问有多少个图的深度优先搜索树是给定的树。

题目代码给定了每个点孩子的访问顺序是编号从小到大，所以可以直接得到每个点的 dfs 序。

考虑 dfs 过程，可以发现树边一定存在，非树边如果是横叉边（两端点在 dfs 树上不是祖孙关系）则一定不存在（否则先 dfs 到其中一端的时候一定会让另一端在这个 dfs 树的子树里），如果是返祖边（祖先到子孙）则在子孙点编号大于它在 dfs 树上所在祖先子树的编号（也就是到祖先点路径的倒数第二个点的编号）时可以存在，否则也不能存在。

综合起来，结论是所有树边一定存在，一部分非树边一定不存在，其余非树边可以存在也可以不存在且每条边状态都互相独立任选。那么答案等于 $2^c$ ，其中 $c$ 是可存在可不存在的非树边个数。我们称这些非树边是合法的。

根据上述讨论，一条非树边合法当且仅当它是祖孙边，且子孙点所属的祖先点的子树的根编号小于子孙点的编号。那么合法的边数总数其实就是满足以下条件的 $(u,v)$ 点对数：

$u$ 是 $v$ 的祖先。
$u\lt v$
$u$ 不是根。（ $u\ne 1$ ）

这样， $u$ 父亲和 $v$ 之间的边是合法的。

要统计这样的点对数，只要统计每个点到根路径上编号小于自己的点数之和。dfs 一遍，用树状数组或者其它数据结构在 dfs 过程中维护当前点到根路径上的点集即可。用权值线段树可以简单做到 $O(n\log n)$ 。但是问题在于你不对拍，你 30 分。

总结：对拍过程：先暴力拍小的，然后不带暴力拍大的测极端数据下是否合法。

T3

先考虑 $k=1$ 的情况，看到这种有多个可以状压的部分，你可能无从下手，但是我们要考虑我们到底要状压什么部分。

考虑贡献，贡献有三部分，固定点内部，固定点与可选点，可选点内部的贡献。

考虑到前两部分的贡献都是可以暴力预处理的，但是后面很难受，这个地方就是我们要特殊处理的部分。

首先考虑这个距离贡献，曼哈顿距离我们将绝对值拆开有：

|a|+|b|=\max(a+b,a-b,-a+b,-a-b).

也就是说，绝对值此时无关紧要，我们只需要考虑安排好每个数每一维正负号的贡献就好了。举个例子，假设已经选好了 $m$ 个点，那么你可以先排序成 $x_1\le x_2\le \cdots\le x_m$ ，然后你按贡献计算 $\sum_{i=1}^m(2i-m-1)x_i=\sum_{i\ne j}|x_i-x_j|$ 。我们实际上只需要枚举 $m!$ 种排列，然后将 $\sum_{i=1}^m(2i-m-1)x_i$ 的最大值算出来。