洛谷5321 [BJOI2019]送别
Luogu LOJ 分析 将每个格点拆成四个点，分别表示从这个点往右走、往下走、往左走、往上走。 对每个点维护一个 $nxt$，表示按照题目中的方式下一步会走到哪个点上。可以发现 $nxt$ 构成了一些有向环，我们想办法对其进行维护。 考虑将环拆掉一条边变成一条有向链，并用 LCT 维护这条链。我们同时维护每一段墙是否存在，并修改连进某个点的链。在修改时，我们首先断掉连进来的边，然后再根据墙...
标签 Link-Cut Tree / LCT 下的文章
- 首页
- Link-Cut Tree / LCT
CF1172E Nauuo and ODT
Codeforces Luogu 分析 考虑计算每种颜色的贡献，即计算每种颜色包含在多少条路径中。 这个东西似乎还是不好算，可以考虑计算每种颜色不包含在多少条路径中。 我们把这种颜色染成白色，其它颜色染成黑色，那么只有黑色连通块内部的点对才满足条件。 于是我们需要支持修改颜色、求黑色连通块大小平方和，使用 QTREE6 一题的方法把颜色放到父边上，LCT 维护子树信息即可。具体细节可以看一看...
JOISC2018 部分题解
高速道路の建設 / Construction of Highway 这个操作长得很像 LCT 中的 access。 于是我们每次只要 access 一下并把所有颜色段拿出来，然后树状数组求逆序对数，再把对应的边连上并把整条重链的颜色赋值为 $c_v$。 因为 access 是均摊 $\mathcal{O}(\log n)$ 的，所以每次颜色段数也是均摊 $\mathcal{O}(\log n...
SPOJ NSUBSTR2 - Substrings II
SPOJ Luogu 分析 首先思路肯定就是建 SAM，询问就找到对应位置然后求 $size$。 然而我们要支持插入，也就是要动态维护 $size$。 可以用 LCT 维护 Parent 树，每次相当于求子树和，用维护子树信息那一套即可。当然也可以直接链修改。 代码 我的写法可能有点奇怪 /kel // ==================================== // au...
洛谷3703 [SDOI2017]树点涂色
Luogu LOJ 分析 可以发现每种颜色一定是一条链，则整棵树相当于被剖分成了若干条链。 考虑 LCT 维护，则 1 操作相当于 access(x)，2 操作相当于询问一条路径上的链数，3 操作相当于求子树中到根路径上链数最大的点。 考虑将 2 操作差分，则只需要用一个数据结构维护每个点到根路径的链数，要求支持区间求最大值。 考虑 access(x) 时对每个点到根路径上的链数的影响。对于...
CF603E Pastoral Oddities
Codeforces Luogu 分析 首先有一个结论：一个大小为偶数的连通块一定存在一个合法的边集，一个大小为奇数的连通块一定不存在一个合法的边集。 证明： 如果连通块大小为奇数，又因为每个点度数都为奇数，所以总度数为奇数，这是不可能的。 如果连通块大小为偶数，此时我们可以先找到一棵生成树，从下往上构造即可。可以发现一定能构造出解。 于是我们只需要保证图中没有大小为奇数的连通块即可。 ...
SPOJ QTREE 系列简要题解
QTREE1 把 $(fa_i,i)$ 的边权作为 $i$ 的点权，然后就是个树剖板子了... 但是注意查询时 LCA 是不能查的，需要判一下。 而且这题竟然不能交 C++ ，然后我改了半个小时才把 C++ 改成 C QAQ QTREE2 DIST 操作只需要维护树上前缀和即可求出答案。 KTH 操作大力讨论一下答案应该在 $u-lca$ 的链上还是 $v-lca$ 的链上，然后倍增上去即...
洛谷3348 [ZJOI2016]大森林
Luogu 分析 假设现在有一个 1 l r x 的操作。我们考虑一下第 $l-1$ 棵树和第 $l$ 棵树、第 $r$ 棵树和第 $r+1$ 棵树的区别。这里假设只有一个这 1 操作。 我们可以这么认为：第 $l$ 棵树是把第 $l-1$ 棵树上生长节点的子树移到第 $l$ 棵树的生长节点上得到的；第 $r+1$ 棵树是把第 $r$ 棵树上生长节点的子树移回去得到的。 那么如果我们可以快速...
洛谷4546 [THUWC2017]在美妙的数学王国中畅游
Luogu LOJ 分析 LCT + 泰勒展开。 取 $x_0=0.5$ ，然后泰勒展开，发现后面的项的贡献很小，可以只保留 $13$ 项。 $\mathrm{LCT}$ 的每个节点维护该点函数的 $n$ 阶导数与子树的 $n$ 阶导数和，这样子查询就可以直接拿出来算。 至于 $n$ 阶导数怎么算... $sin'(x)=cos(x),\ cos'(x)=-sin(x)$ $(e^x)'=...