洛谷4747 [CERC2017]Intrinsic Interval
LuoguGym分析析合树模板题。如果两个点在析合树上的 LCA 是析点，那么答案就是这个析点对应的段；否则还要找到两个点所在的两棵子树，LCA 的儿子序列中这两个子树间的子序列才是答案。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // =...
标签 树链剖分 下的文章
- 首页
- 树链剖分
洛谷4606 [SDOI2018]战略游戏
LuoguLOJ分析考虑哪些点是满足条件的。可以发现任意两个关键点路径上的割点都满足条件。于是可以考虑广义圆方树，因为两个点路径上的割点即对应在圆方树路径上的圆点。又因为关键点两两之间路径的并就等于这些关键点的虚树，所以我们把问题转化成了求虚树上圆点个数（等价于求点权和）。这个并不好做，但是我们知道边权和是很好求的（等于所有点按 DFS 序排序后相邻两个点的距离之和再除以二），所以可以考虑把...
CF757G Can Bash Save the Day?
CodeforcesLuogu分析考虑把每个询问拆成 $\sum_{i=1}^r\operatorname{dis}(p_i,u)-\sum_{i=1}^{l-1}\operatorname{dis}(p_i,u)$。我们考虑怎么求 $\sum_{i=1}^t\operatorname{dis}(p_i,u)$，这个东西可以拆成 $t\times dep_u+\sum_{i=1}^t dep...
洛谷5891 Fracture Ray
Luogu分析对于每个数 $x$ 从 $x+\operatorname{count}(x)$ 向 $x$ 连边，则应该是一个森林。为了方便我们再建一个点向每棵树的根连边。然而点数是 $2^{30}$ 级别的，所以并不能直接拿树剖+线段树搞。但实际上只有 $2\times 10^5$ 个操作，所以可以考虑建虚树，并对虚树上的每个点求出 $cnt_x$ 表示向上走多少条边能到达虚树上的父亲 $f...
CF487E Tourists
CodeforcesLuogu分析可以发现，在从 $u$ 走到 $v$ 的过程中如果经过了一个点双联通分量，那么对于其中的每个点都存在一条经过它的路径。因此，我们一定会经过每个点双中权值最小的点。从而可以想到广义圆方树。对于每个方点，它的权值应为与它相连的圆点中的最小值。这样子查询直接树剖+线段树即可。因为有修改圆点权值的操作，用 std::multiset 维护每个方点相连的圆点的权值，修...
洛谷3703 [SDOI2017]树点涂色
LuoguLOJ分析可以发现每种颜色一定是一条链，则整棵树相当于被剖分成了若干条链。考虑 LCT 维护，则 1 操作相当于 access(x)，2 操作相当于询问一条路径上的链数，3 操作相当于求子树中到根路径上链数最大的点。考虑将 2 操作差分，则只需要用一个数据结构维护每个点到根路径的链数，要求支持区间求最大值。考虑 access(x) 时对每个点到根路径上的链数的影响。对于当前的 $x...
LOJ3280 「JOISC 2020 Day4」首都城市
LOJ分析考虑建一个图，即如果某两个颜色为 $i$ 的点的路径上存在一个颜色为 $j$ 点，则从 $i$ 向 $j$ 连一条边。那么一条边 $(u,v)$ 的实际意义是要想把颜色为 $u$ 的点连通，则必须把 $u,v$ 合并。考虑一个强连通分量，显然其中任意一种颜色想要连通都只能将其它 $sz-1$ 个颜色合并，因此一个强连通分量需要合并 $sz-1$ 次。于是我们缩点并将 $sz-1$ ...
CF504E Misha and LCP on Tree
CodeforcesLuogu分析考虑对原树树链剖分，则两条路径都拆成了 $\mathcal{O}(\log n)$ 个区间。每次取最前面的区间出来比较，如果相同则消掉一个区间，否则答案在该区间内，二分即可。问题在于如何求出某条重链的哈希值。因为重链的 DFS 序是连续的一段，因此可以将树按 DFS 序拍成序列，然后正反各做一遍哈希，则一条重链的哈希值相当于某个区间的哈希值。代码实现有些复杂...
洛谷4689 [Ynoi2016]这是我自己的发明
Luogu分析以 $1$ 为根 DFS 一次，那么换根后任意子树对应 DFS 序上至多两个区间。因此对于两棵子树的询问可以拆成 DFS 序上若干对区间的询问。设 $f(l_1,r_1,l_2,r_2)$ 表示 DFS 序上 $[l_1,r_1]$ 和 $[l_2,r_2]$ 的答案，容斥一下得到这样就可以直接莫队了。令块大小为 $\frac{n}{\sqrt{m}}$，则莫队的复杂度为 $\...
洛谷1505 [国家集训队]旅游
Luogu分析把边权放到点上，树剖之后就只需要写一个支持单点赋值、区间取相反数、区间求和、区间求最小值、区间求最大值的线段树了。这个东西还比较好维护。一个技巧是将三个要维护的东西封装到一个 struct 里然后重载 +，可以有效减少代码量。关键代码大概是这样子：int invv[N<<2]; // 取相反数的标记 struct node { int sumv,minv,maxv;...