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，重复以下过程：递归处理所有轻儿子，并消去贡献。递归处理重儿子，并保留贡献。将轻儿子的信息合并到重儿子保留的贡献中。若当...
洛谷3979 遥远的国度
Luogu分析这种带换根的树上操作题就是 LCT板子 分类讨论...首先那个链修改是不受换根影响的，我们只需要讨论子树查询。设以 $1$ 为根时 $u$ 子树的点的 dfs 序在 $[st_u,ed_u]$ 内。假设查询的是 $u$ 子树，根是 $rt$，那么大概有以下几种情况：$u=rt$，直接查所有点的最小值即可。$\operatorname{lca}(u,rt)\neq u$，此时 $...
SPOJ COT2 - Count on a tree II
SPOJLuogu分析树上莫队板子题...？首先把树的欧拉序爬下来。设 $st_u$ 表示第一个 $u$ 的位置，$ed_u$ 表示最后一个 $u$ 的位置。考虑一个询问 $(u,v)$ 怎么统计。为了方便，设 $st_u<st_v$ 。如果 $lca(u,v)=u$ ，那么 $(u,v)$ 路径上的点就是欧拉序的 $[st_u,st_v]$ 中只出现过一次的点，莫队统计即可。如果 $...
SPOJ GSS 系列简要题解
GSS1线段树上维护以下 $4$ 个东西：区间和区间最大前缀和区间最大后缀和区间最大子段和合并两个区间应该比较简单，这里不再赘述。GSS2这题就很神仙了。把所有询问离线并按右端点排序，然后从左往右扫。对于线段树的每个叶子节点 $[i,i]$，假设当前扫到了 $p$ ，那么该节点存的是 $\displaystyle\sum_{j=i}^pa_j$ 。设 $pre_i$ 表示上一个和 $a_i$...
SPOJ QTREE 系列简要题解
QTREE1把 $(fa_i,i)$ 的边权作为 $i$ 的点权，然后就是个树剖板子了...但是注意查询时 LCA 是不能查的，需要判一下。而且这题竟然不能交 C++ ，然后我改了半个小时才把 C++ 改成 C QAQQTREE2DIST 操作只需要维护树上前缀和即可求出答案。KTH 操作大力讨论一下答案应该在 $u-lca$ 的链上还是 $v-lca$ 的链上，然后倍增上去即可求出。所以只...