P4338:[ZJOI2018]历史 – 题解

主要思路

ZJOI 的题质量都好高啊!真的都是很棒的题。

其实这个覆盖的东西就相当于在 LCT 上进行 Access 时轻重链切换的次数。我们考虑静态的问题,对于点 \(u\) 来说,如果子树内有多个来自不同儿子子树内的子代节点,那么就需要进行合理的分配来把这个轻重链切换次数搞到最大。

转换一下就是两两不同颜色的点进行配对的最大值。设 \(S_0 = a_u, S_i = [\text{第 } i \text{个子树内的 access 次数之和}]\)。那么答案其实就是 \(\max\{ \sum_{i = 0}^m S_i – 1, 2(\sum_{i = 0}^m S_i – \max_{i \in [0, m]} S_i) \}\),前者是啥都不考虑,后者是连接到一个子节点。后者成为最大值的条件其实就是要成为重儿子。我们考虑维护这个东西。

发现其实我们用贪心的分配方案进行轻重链剖分时,复杂度也是对的。因为被贪心选择的那个子节点确实也是个重儿子,根据树链剖分那一套理论这个复杂度是成立的。

当我们进行修改时,我们就需要用 Access 操作来进行判断和修改。我们需要判断是否存在虚子树中的点成为重儿子,然后进行切换。

继续阅读P4338:[ZJOI2018]历史 – 题解

Codeforces 1172E:Nauuo and ODT – 题解

主要思路

写起来还是有点麻烦的,LCT + 离线处理放在一起就比较难写。

首先我们可以考虑离线,这样我们就可以分颜色来考虑这个问题。假设现在在颜色 \(c\),那么我们需要统计每个时刻不包含本颜色的路径数量,并且做差分(也就是做每个时刻)。此时颜色只分黑白,那么我们只需要把本颜色的点做成白色,然后统计每个黑点的连通块大小的平方即可。

继续阅读Codeforces 1172E:Nauuo and ODT – 题解

LibreOJ 2187:「SHOI2014」三叉神经树 – 题解

主要思路

先建好树,大概思考一下应该可以推导出:倍增找标记点,然后根到区间修改。然而正解也是这样写,只不过细节有点多,我在这里提一下:回答询问\(x\)时,先把他父亲提到根,然后找最近的点;找到了就把深度大的全部打标记反过来。

继续阅读LibreOJ 2187:「SHOI2014」三叉神经树 – 题解

POJ1639:Picnic Planning 题解

大体思路

做过 LCT 么?(做过基本上就可以切这一道题)

考虑把跟节点先去掉,然后会产生很多个联通块:每一个连通块求出最小生成树,然后找到整个连通块与根节点连接的最小边,连上。

之后如果还剩下一定的可以使用的度数,我们可以考虑用根节点剩余的边去更新整个最小生成树。具体而言,我们找到了一个\((1, v)\)未使用的边,然后我们找\(1 \to v\)上所有的边,找到一个差值最大的。如果这个差值是正数,那么加入这条边,删去之前的边,就会发现答案减掉了这个正差值。不停重复就可以得到答案。

继续阅读POJ1639:Picnic Planning 题解

LCT 的一类题目

LCT 简述

LCT (Link Cut Tree) 是一种维护树链的灵活的数据结构。与线段树不同的是,LCT 一般使用 Splay 这种非常优雅、灵活的数据结构来维护树链。因为 LCT 支持动态增边、删边,所以很多题目就可以打破一些限制进行求解。

继续阅读LCT 的一类题目