MCOI R4 B Solution

· · 题解

真不会写题面了，出题人语文没救/ll

算法 1：

输出 q 个 0，复杂度为读入复杂度 O(n+q)。

当然对于链是正确的，期望得 1 分。

算法 2：

对于菊花，只能从两个方向走，分类讨论一下。

复杂度 O(n+q)，期望得 9 分。

算法 3：

将每一个区域看作一个点建图。

考虑每一条直线，将两侧的区域连一条代价为 1 的边。

每次询问跑 BFS 即可。

时间复杂度 O(nq)，期望得 20 分。

算法 4：

当树为完全二叉树时，可以将区域按照最顶上的点进行编号。

然后有一个 observation：对于一个点，在最优移动中，最顶上的点一定一直是 u 或 v 的祖先。

由于这是二叉树，所以直接按区域编号做一个暴力的 dp 的复杂度是 O(\log n)。

于是就可以做了。

期望得 20 分。

当然如果你把区域换成用边表示，缩掉链，并在 dp 的方程上稍微做一点修改就可以过掉前面的所有点并获得 40 分。

算法 5：

受到算法 4 的启发，考虑将 u\rightarrow \text{lca}(u,v) 和 v\rightarrow \text{lca}(u,v) 单独提取出来。

如果能做出这两条链的结果，那么就变成了菊花上的问题。

那么怎么求这两条链的结果呢？

首先把链提取出来，然后我们发现，不与这条链直接相连的节点都是没有用的，因为过它们的边肯定不优于过直接与链相连的边。

现在就可以考虑一个倍增形式的 DP。

定义一条边的「左区域」为子节点编号更小的区域，同时另外一个区域就是「右区域」。

设 dp_{u,k,0/1,0/1} 表示从 u\rightarrow f_u 的边的左区域（ 0 ）/右区域（ 1 ）走到 f_u^{2^k}\rightarrow f_u^{2^k+1} 的左区域（ 0 ）/右区域（ 1 ）的最小代价。

那么如何由 dp_{u,k-1} 转移至 dp_{u,k}？

可以分类讨论是否跨过中间的边，然后把两条路径连接起来。

于是我们就有如下转移：（由于比较复杂，所以就贴代码了）

Segnode operator + (const Segnode& b) const {
    Segnode res;
    int v1 = Min(b.lldis, b.rldis + 1), v2 = Min(b.lldis + 1, b.rldis), v3 = Min(b.lrdis, b.rrdis + 1), v4 = Min(b.lrdis + 1, b.rrdis);
    res.lldis = Min(lldis + v1, lrdis + v2);
    res.lrdis = Min(lldis + v3, lrdis + v4);
    res.rldis = Min(rldis + v1, rrdis + v2);
    res.rrdis = Min(rldis + v3, rrdis + v4);
    return res;
}

其中 lldis 就是左区域到左区域的最短路径长度，lrdis 是左区域到右区域的最短路径长度，rldis 是右区域到左区域的最短路径长度，rrdis 是右区域到右区域的最短路径长度。

转移思路可以理解为不跨过中间的边，就是左接左，右接右；跨过中间的边，就是左接右，右接左，然后再加 1 代表跨过中间的边产生的代价。

那么边界 dp_{u,0} 就直接讨论一下 f_u 的度数即可。

int lw = faid[i] - 1, rw = g[fa[i][0]].size() - faid[i];
dp[i][0].lldis = Min(lw, rw + 2);
dp[i][0].lrdis = 1 + Min(lw, rw);
dp[i][0].rldis = 1 + Min(lw, rw);
dp[i][0].rrdis = Min(lw + 2, rw);

于是我们对每一组询问倍增，然后就变成了菊花上的询问，故用菊花的方式 O(1) 合并即可。

时间复杂度 O((n+q)\log n)，期望得分 99 分。

算法 6：

在算法 5 的基础上继续改进，考虑长链剖分。

类似树上 k 级祖先，保存链顶往上链长个 dp 值和往下链长个 dp 值。

剖分完之后再结合倍增，问题转化为区间求和，但是信息不可减，不能交换，只有结合律。

直接上 sqrt tree，复杂度为 O(n\log n+q)。

细节非常多，尤其要注意在预处理时倒序求和（\text{sum}(l,r)=a_r+a_{r-1}+\cdots+a_l\neq a_l+a_{l+1}+\cdots+a_r），如果顺序错误（应该）会被第二个样例卡掉。

还有一些神奇的卡常方式，例如链长为 1 的长链不需要保存，以及将单链缩为一个点。

然后要注意 sqrt tree 的写法，如果你直接用 vector 之类的东西去建树那么时空稳稳炸飞，更好的写法是按层开数组。

然后是一个时间上的卡常，由于在询问的链的长度的二进制表示中 1 位数量比较小的时候倍增快于正解，所以正解做了一个分治，在 k 的二进制表示只有 \leq 3 个 1 的时候直接倍增。

最后，在做完上面的卡常之后，可以保证 sqrt tree 查询的区间长度 \geq 15，所以 分块只需要分到块长等于 8。这样可以砍下很多空间。

更进一步，链长 \leq 7 的长链也全都不需要存了。

巨量细节和卡常也是我为什么只给这个 subtask 1 分（

期望得分 100 分。

核心代码

顺便推一下 Ace Combat 系列，挺好玩的，而且 7 代支持 PC，有意愿的可以一试（

AC6 Ace Of Aces M09 也是值得一试的一作，号称是皇中皇极端变态的难度的巅峰，如果有神仙过了给我来一组图（