洛谷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;...
洛谷1600 天天爱跑步
LuoguLOJ分析脑子不够，数据结构来凑我们把每个人的路径拆成上行（$s\to lca$）和下行（$lca\to t$）两部分。先考虑上行部分，如果一个人能被 $i$ 点的观察员观察到则有 $dep_s-dep_i=w_i$，移项得到 $dep_s=w_i+dep_i$。再考虑下行部分，如果一个人能被 $i$ 点的观察员观察到则有 $dis(s,t)-dep_t+dep_i=w_i$，移项...
洛谷2680 运输计划
Luogu分析显然可以二分答案。那么我们只需要判断是否存在一条边，满足它被所有长度 $>mid$ 的运输计划覆盖，而且这些运输计划长度减掉它的长度后 $\leq mid$。显然我们会选所有满足「被所有长度 $>mid$ 的运输计划覆盖」的边中长度最大的那个，因此我们只需要想一想怎么求出一条边被覆盖的次数。这个直接树上差分即可，当然也可以像我一样写树剖+线段树（但是不吸氧可能会 T...
CF600E Lomsat gelral
CodeForces分析树上启发式合并板子题。维护一个 $cnt_i$ 表示第 $i$ 种颜色的出现次数，$num_i$ 表示有多少种颜色出现 $i$ 次，$sum_i$ 表示所有颜色出现 $i$ 次的节点的编号和。这样子计算贡献显然是 $O(1)$ 的。那么在树上 DFS，重复以下过程：递归处理所有轻儿子，并消去贡献。递归处理重儿子，并保留贡献。将轻儿子的信息合并到重儿子保留的贡献中。若当...