LuoguGym分析析合树模板题。如果两个点在析合树上的 LCA 是析点,那么答案就是这个析点对应的段;否则还要找到两个点所在的两棵子树,LCA 的儿子序列中这两个子树间的子序列才是答案。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // =...
LuoguLOJ分析考虑哪些点是满足条件的。可以发现任意两个关键点路径上的割点都满足条件。于是可以考虑广义圆方树,因为两个点路径上的割点即对应在圆方树路径上的圆点。又因为关键点两两之间路径的并就等于这些关键点的虚树,所以我们把问题转化成了求虚树上圆点个数(等价于求点权和)。这个并不好做,但是我们知道边权和是很好求的(等于所有点按 DFS 序排序后相邻两个点的距离之和再除以二),所以可以考虑把...
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...
Luogu分析对于每个数 $x$ 从 $x+\operatorname{count}(x)$ 向 $x$ 连边,则应该是一个森林。为了方便我们再建一个点向每棵树的根连边。然而点数是 $2^{30}$ 级别的,所以并不能直接拿树剖+线段树搞。但实际上只有 $2\times 10^5$ 个操作,所以可以考虑建虚树,并对虚树上的每个点求出 $cnt_x$ 表示向上走多少条边能到达虚树上的父亲 $f...
CodeforcesLuogu分析可以发现,在从 $u$ 走到 $v$ 的过程中如果经过了一个点双联通分量,那么对于其中的每个点都存在一条经过它的路径。因此,我们一定会经过每个点双中权值最小的点。从而可以想到广义圆方树。对于每个方点,它的权值应为与它相连的圆点中的最小值。这样子查询直接树剖+线段树即可。因为有修改圆点权值的操作,用 std::multiset 维护每个方点相连的圆点的权值,修...
LuoguLOJ分析可以发现每种颜色一定是一条链,则整棵树相当于被剖分成了若干条链。考虑 LCT 维护,则 1 操作相当于 access(x),2 操作相当于询问一条路径上的链数,3 操作相当于求子树中到根路径上链数最大的点。考虑将 2 操作差分,则只需要用一个数据结构维护每个点到根路径的链数,要求支持区间求最大值。考虑 access(x) 时对每个点到根路径上的链数的影响。对于当前的 $x...
LOJ分析考虑建一个图,即如果某两个颜色为 $i$ 的点的路径上存在一个颜色为 $j$ 点,则从 $i$ 向 $j$ 连一条边。那么一条边 $(u,v)$ 的实际意义是要想把颜色为 $u$ 的点连通,则必须把 $u,v$ 合并。考虑一个强连通分量,显然其中任意一种颜色想要连通都只能将其它 $sz-1$ 个颜色合并,因此一个强连通分量需要合并 $sz-1$ 次。于是我们缩点并将 $sz-1$ ...
CodeforcesLuogu分析考虑对原树树链剖分,则两条路径都拆成了 $\mathcal{O}(\log n)$ 个区间。每次取最前面的区间出来比较,如果相同则消掉一个区间,否则答案在该区间内,二分即可。问题在于如何求出某条重链的哈希值。因为重链的 DFS 序是连续的一段,因此可以将树按 DFS 序拍成序列,然后正反各做一遍哈希,则一条重链的哈希值相当于某个区间的哈希值。代码实现有些复杂...
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}}$,则莫队的复杂度为 $\...
Luogu分析把边权放到点上,树剖之后就只需要写一个支持单点赋值、区间取相反数、区间求和、区间求最小值、区间求最大值的线段树了。这个东西还比较好维护。一个技巧是将三个要维护的东西封装到一个 struct 里然后重载 +,可以有效减少代码量。关键代码大概是这样子:int invv[N<<2]; // 取相反数的标记 struct node { int sumv,minv,maxv;...