方知蓦然回首之时
那人却已不在灯火阑珊处

标签 树链剖分 下的文章

傻逼题,CF 的数据是假的,不开 std::multiset 都可以过。

发现我们直接缩成一棵广义圆方树然后进行维护。修改点权的时候如果我们暴力修改圆点周围的方点显然可能挂掉,但是如果我们的方点只存圆方树上孩子的信息,那么就只用更新 O(1) 次了,这样的话在求 u \rightarrow v 的路径的时候判断一下 LCA 是不是方点即可。时间复杂度 O(n \log^2 n)

READ MORE

傻逼题,写来放松身心。

考虑到 \displaystyle dep_u^k = \sum_{i=0}^{\infty} dep_{fa^i(u)}^k - dep_{fa^{i+1}(u)}^k,假设我们要求 \displaystyle dep_{\operatorname{lca}(u, v)},可以把 u1 的路径上每个点 x 加上 dep_x^k - dep_{fa(x)}^k 的权值,查询时从 v 向根节点跳把沿途的权值加上即可。

离线所有查询到 x 上,扫描 x,树剖维护修改和查询即可。

READ MORE

要求维护一棵树,支持:

  • 给定 x, y, w,其中 w \in \{-1, 1\},将 xy 链上所有点权加上 w
  • 给定 x, y,查询 xy 的链上点权大于 0 的点的个数
  • 给定 x,查询 x 的子树内点权大于 0 的点的个数

n \leq 100000,时限 2s 。

READ MORE

可能有点假,但没有用线段树......

首先肯定会在 LCA 处集合,通过树剖 + bitset 维护出可选的集合。然后利用 Hall 定理进行完美匹配统计答案。可以发现直接树剖 + 暴力跳是 O(n ^ 2) 的,所以限制树链的长度至多为 S ,则复杂度为:O(n + qcS\times\frac{m}{32} + qc \times \frac{n}{S} + q \times 2^c \times \frac{m}{32}) ,取 S = \sqrt n

试了一下可以被极端数据卡掉,但是 BZOJ 上的数据是随机生成的所以跑的飞快 QAQ ...

READ MORE

本题有虚树做法,基本思想差不多,但个人感觉还是换根树剖清真一点 233。

定义一组询问的根节点为这组询问的一号节点。

一个点会对答案产生贡献,当且仅当这个点到这组节点的其他节点的距离大于等于这个节点到这组询问的根节点的距离。

假设当前我们做到根节点为 root ,当前节点为 u 的情况,找出这条路径的中点为 mid ,那么肯定不会对答案产生贡献的点即整颗树 root 为根节点时 mid 这个节点的整颗子树。就是一个简单的换根树剖,乱搞一下即可。

READ MORE