洛谷5321 [BJOI2019]送别
LuoguLOJ分析将每个格点拆成四个点，分别表示从这个点往右走、往下走、往左走、往上走。对每个点维护一个 $nxt$，表示按照题目中的方式下一步会走到哪个点上。可以发现 $nxt$ 构成了一些有向环，我们想办法对其进行维护。考虑将环拆掉一条边变成一条有向链，并用 LCT 维护这条链。我们同时维护每一段墙是否存在，并修改连进某个点的链。在修改时，我们首先断掉连进来的边，然后再根据墙的情况修改...
标签 Link-Cut Tree / LCT 下的文章
- 首页
- Link-Cut Tree / LCT
CF1172E Nauuo and ODT
CodeforcesLuogu分析考虑计算每种颜色的贡献，即计算每种颜色包含在多少条路径中。这个东西似乎还是不好算，可以考虑计算每种颜色不包含在多少条路径中。我们把这种颜色染成白色，其它颜色染成黑色，那么只有黑色连通块内部的点对才满足条件。于是我们需要支持修改颜色、求黑色连通块大小平方和，使用 QTREE6 一题的方法把颜色放到父边上，LCT 维护子树信息即可。具体细节可以看一看官方题解中的...
JOISC2018 部分题解
高速道路の建設 / Construction of Highway这个操作长得很像 LCT 中的 access。于是我们每次只要 access 一下并把所有颜色段拿出来，然后树状数组求逆序对数，再把对应的边连上并把整条重链的颜色赋值为 $c_v$。因为 access 是均摊 $\mathcal{O}(\log n)$ 的，所以每次颜色段数也是均摊 $\mathcal{O}(\log n)$ ...
SPOJ NSUBSTR2 - Substrings II
SPOJLuogu分析首先思路肯定就是建 SAM，询问就找到对应位置然后求 $size$。然而我们要支持插入，也就是要动态维护 $size$。可以用 LCT 维护 Parent 树，每次相当于求子树和，用维护子树信息那一套即可。当然也可以直接链修改。代码我的写法可能有点奇怪 /kel// ==================================== // author: M_...
洛谷3703 [SDOI2017]树点涂色
LuoguLOJ分析可以发现每种颜色一定是一条链，则整棵树相当于被剖分成了若干条链。考虑 LCT 维护，则 1 操作相当于 access(x)，2 操作相当于询问一条路径上的链数，3 操作相当于求子树中到根路径上链数最大的点。考虑将 2 操作差分，则只需要用一个数据结构维护每个点到根路径的链数，要求支持区间求最大值。考虑 access(x) 时对每个点到根路径上的链数的影响。对于当前的 $x...
LOJ6038 「雅礼集训 2017 Day5」远行
LOJ分析根据一个结论可以知道，距离树上一点最远的点一定是直径的两个端点之一。于是可以用并查集维护连通块，同时维护每个连通块的直径的端点，合并两个连通块时在六条可能的直径中取个 $\max$ 即可。需要支持加边和询问两点间距离，可以用 LCT 实现。代码// ==================================== // author: M_sea // web...
CF603E Pastoral Oddities
CodeforcesLuogu分析首先有一个结论：一个大小为偶数的连通块一定存在一个合法的边集，一个大小为奇数的连通块一定不存在一个合法的边集。证明：如果连通块大小为奇数，又因为每个点度数都为奇数，所以总度数为奇数，这是不可能的。如果连通块大小为偶数，此时我们可以先找到一棵生成树，从下往上构造即可。可以发现一定能构造出解。于是我们只需要保证图中没有大小为奇数的连通块即可。考虑一个类似 Kru...
SPOJ QTREE 系列简要题解
QTREE1把 $(fa_i,i)$ 的边权作为 $i$ 的点权，然后就是个树剖板子了...但是注意查询时 LCA 是不能查的，需要判一下。而且这题竟然不能交 C++ ，然后我改了半个小时才把 C++ 改成 C QAQQTREE2DIST 操作只需要维护树上前缀和即可求出答案。KTH 操作大力讨论一下答案应该在 $u-lca$ 的链上还是 $v-lca$ 的链上，然后倍增上去即可求出。所以只...
洛谷5024 保卫王国
LuoguLOJ分析动态 DP 。我们要求的是最小点覆盖，这个东西就等于权值和减去最大权独立集。那么就是差不多就是【模板】动态DP了。强制选的话，就把权值改成 $\infty$ ；强制不选的话，就把权值改成 $-\infty$ 。然后就做完了。代码// =================================== // author: M_sea // website: h...
NOIP2018简要题解
PJ标题统计按照题意模拟即可。龙虎斗枚举即可。记得开 $\texttt{long long}$ 。摆渡车设 $f[i]$ 表示前 $i$ 时刻的答案，容易得到 $\displaystyle f[i]=\min_{j\leq i-m}\{f[j]+\sum_{j<k\leq i}i-t_k\}$ 。直接前缀和优化即可得到 $50$ 分。考虑优化。可以发现 $j$ 只需要从 $i-2m+1...