T1 编辑字符串

比较简单的题，想通了就可以。

简单来说是这样一件事，因为我们可以自由的交换每一个块里面的元素，那么就贪心的一一配对即可。

就那样例举例：

1 2	0 1 1\|1\|0\|1 1\|1\|1 0\|1\|0

这个是分完组的结果，因为单独的一个块和不能移动的元素一样，都是固定的，所以我们认为他们都是同一类东西，都是用一个块标记。

贪心的思路很显然了。就是从左边往右一一对应，对于他们所在的块分别配队对应的01即可。

T2 遗失的赋值

首先注意到单个的一元限制对二元限制的限制是没有意义的，只有两个一元限制才可能得出二元限制的方案数。
并且关注到“在 $n$ 个数之间插入了 $n-1$ 条限制”所以他一定是一个链式结构。

所以我们定义函数 $f(x)$ 表示在一个固定左右端点的区间内放下 $x$ 个二元限制的方案数。
接下来开始准备推导式子。

分两种情况讨论：

二元限制的要求是从起点开始的，所以只要起点就不符合规定，剩下的所有二元限制都是可以乱填的。也就是：$v\times (v-1) \times (v^2)^{x-1}$，表示起点的方案数乘以剩下的全部乱填的方案数。
接下来是有限制的情况，相当于是转换为了一个子问题，方案数为 $v\times f(x-1)$。
那么式子也就如此了。 $f(x)=v^{2x}−v^{2x−1}+v\times f(x−1)$ 做到这里的话已经成功一半了。注意到题目给我们 $n$ 的大小为 $10^9$，这个式子也显然可以用矩阵快速幂快速计算。

但还有一个简单的做法就是进一步对式子进行推导。

$\begin{aligned} f(x-1) &= v^{2x-2}-v^{2x-3} + v\times f(x-2)\\ \\ f(x) &= v^{2x} - v^{2x-1} + v\times f(x-1)\\ &= v^{2x} - v^{2x-1} + v\times (v^{2x-2}-v^{2x-3} + v\times f(x-2))\\ &= v^{2x}-v^{2x-1}+v^{2x-1}-v^{2x-2}+v^2\times f(x-2)\\ &= v^{2x} - v^{2x-2} + v^2\times f(x-2) \end{aligned}$

我们会发现这个式子和一开始的形式超级像，所以考虑再往下推一个：

$\begin{aligned} f(x-2) &= v^{2x-4}-v^{2x-5} + v\times f(x-3)\\ \\ f(x) &= v^{2x} - v^{2x-2} + v^2\times f(x-2)\\ &= v^{2x} - v^{2x-2} + v^2\times (v^{2x-4}-v^{2x-5} + v\times f(x-3))\\ &= v^{2x} - v^{2x-2} + v^{2x-2} - v^{2x-3} + v^3\times f(x-3)\\ &= v^{2x} - v^{2x-3} + v^3\times f(x-3) \end{aligned}$

规律显然了，如果还看不出来可以考虑再推一个。

$\begin{aligned} f(x) &= v^{2x} − v^{2x−1} + v\times f(x−1)\\ f(x) &= v^{2x} - v^{2x-2} + v^2\times f(x-2)\\ f(x) &= v^{2x} - v^{2x-3} + v^3\times f(x-3)\\ \dots\\ f(x) &= v^{2x} - v^{2x-k} + v^k\times f(x-k) \end{aligned}$

有了这个式子有什么用呢？很简单，可以让我们的递推式编成通项公式。
直接代入 $k=x-1$，因为边界条件是 $f(1) = v^2-v+1$，那么就有：

$\begin{aligned} f(x) &= v^{2x} - v^{x+1} + v^{x-1} \times (v^2 - v + 1)\\ &= v^{2x} - v^{x+1} + v^{x+1} - v^x + 1\\ &= v^{2x} - v^x + 1 \end{aligned}$

用快速幂计算即可。

T3 树的遍历

真的只会最基础的分。

注意到当起点确定的时候，对于每个点都有出度排列种走法，用乘法原理即可。

T4 树上查询

基础分是好拿的。

直接 $n^2$ 暴力枚举两个点然后求 LCA 即可。因为一个连续区间的 LCA 一定可以抽象为两个点的 LCA，这样做的时间复杂度为 $O(Q\times n^2\log n)$，可以拿到 8 分。

还有一个接近正解的关键性质：

$\operatorname{dep}_{\operatorname{LCA}([l,r])} = \min_{1\le i\lt n}\operatorname{dep}_{\operatorname{LCA}(\{i, i+1\})}$

其中 $\operatorname{LCA}(S)$ 表示集合 $S$ 中所有节点的最近公共祖先；$\operatorname{dep}(u)$ 表示节点 $u$ 的深度，根节点的深度为 $1$。

接下来进行简单的证明：

证明：$\operatorname{dep}_{\operatorname{LCA}([l,r])} = \min_{1\le i\lt n}\operatorname{dep}_{\operatorname{LCA}(\{i, i+1\})}$
考虑将问题拆分为两个部分：

$\operatorname{dep}_{\operatorname{LCA}([l,r])} \ge \min_{1\le i\lt n}\operatorname{dep}_{\operatorname{LCA}(\{i, i+1\})}$

$\operatorname{dep}_{\operatorname{LCA}([l,r])} \le \min_{1\le i\lt n}\operatorname{dep}_{\operatorname{LCA}(\{i, i+1\})}$
其中，显然分支二比较好证，所以考虑从它开始突破。

为了方便表述，现在规定如下几个符号：

$L$：$[l,r]$ 中所有节点的 $LCA$;

$L_i$：$\operatorname{LCA}(\{i, i+1\})$；

$M$：满足 $\min_{1\le i\lt n}\operatorname{dep}_{L_i}$ 的 $i$ 节点编号。

证明分支1：$\operatorname{dep}_L \le \min_{1\le i\lt n}\operatorname{dep}_{L_i}$
由 $L$ 的定义，$L$ 必然是所有 $L_i$ 的祖先，所以 $dep_l \le \min_{1\le i\lt n}\operatorname{dep}_{L_i}$，命题成立。

证明分支2：$dep_L\ge \min_{1\le i\lt n}\operatorname{dep}_{L_i}$
对于 $M$ 节点考虑往左右方向拓展。不妨先尝试往右拓展。
因为 $M$ 的定义，我们知道 $\operatorname{dep}_{L_M} \le \operatorname{dep}_{L_{M+1}}$，而 $L_M$ 是节点 $M$ 和 $M+1$ 的最近公共祖先，$L_{M+1}$ 是节点 $M+1$ 和 $M+2$ 的最近公共祖先，也就是说 $L_M$ 和 $L_{M+1}$ 都在节点编号为 $M+1$ 的节点的祖先方向。即 $L_M$ 是所有节点的公共祖先（注意这里只能证明是公共祖先，而不能证明是最近公共祖先）。
往左拓展同理。
再根据 $L$ 的定义我们知道他是所有结点的最近公共祖先，而 $L_M$ 却是所有节点的公共祖先，不难理解 $L_M$ 一定是 $L$ 的祖先，即 $\operatorname{dep}_{L} \ge \operatorname{dep}_{L_M}$ 该分支得证。

最后一步了，由于我们得到了两个不等式，其解集显然只有 $\operatorname{dep}_L = \min_{1\le i\lt n}\operatorname{dep}_{L_i}$，所以原命题得证。