警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

LCT 第一轮复习 - LCT

因为前面那篇 LCT Blog 问题太多了,所以重写一篇。

目前完成的状态

  • 维护链上信息
    • P3690 Link Cut Tree
    • P1501 Tree II
    • P3203 弹飞绵羊
    • P2486 染色
    • P4332 三叉神经树
    • P5354 由乃的OJ
  • 维护子树信息
    • P4219 大融合
    • LOJ #558 我们的 CPU 遭到攻击
  • 维护生成树
    • UOJ #274 温暖会指引我们前行
  • 维护 DCC / 广义圆方树
    • P2542 航线规划
    • P4320 道路相遇
    • U76146 鱼题

一些坑

我原来的 LCT 板子是这么写的:

……然后里面的 cut 和 fr 是错的。

然后 findroot 如果不 splay,可能会导致复杂度爆炸;如果不 pushdown,标记可能没有释放完全。

维护链上信息

题意

给一棵树,支持 link、cut、链上异或和、单点修改。

解法

板子。

代码

P1501 Tree II

题意

给一棵树,支持链上加、链上乘、链上和、link 和 cut。保证操作合法。

线段树 2 上树……

解法

线段树 2 怎么做,这题就怎么做。

然后这题模数的平方在 unsigned 范围。建议 #define int unsigned

代码

P3203 弹飞绵羊

题意

给一棵树,支持换父亲和查深度。保证操作合法。

解法

还是板子。换父亲就是 cut 然后 link。查深度就是 split 之后的 size。

其实根本不需要换根,直接 access 然后 splay 就好了。

没事嘛,假装在检验自己的背诵成果就好了

代码

P2486 染色

题意

给一棵树,支持链上染色,求链上颜色数。

树点涂色严格弱化版

解法

对 Splay 里的每个区间维护 左端颜色右端颜色颜色数量 就好了。

注意 reverse 的时候要 swap 左端颜色右端颜色

代码

P4332 三叉神经树

题意

给一棵 \(3n+1\) 个点的满三叉树,其中 \(>n\) 的点都是叶子。\(\forall_{x\le n}\),令 \(f_x=\left[\sum_{i\in son_x}f_i\ge 2\right]\)。给定叶子的 \(f\),支持两种操作:

  • 反转一个叶子的 \(f\)
  • 查询 \(f_1\)

\(1\le n,q\le5\times10^5\)

解法

难题。

首先注意到每次修改操作,都会改变 从该叶子出发的一条,向根的链上的 \(\mathbf f\)

令修改的点为 \(x\),它的父亲为 \(y\)\(s_x=\sum_{i\in son_x}f_i, x\le n\)。分类讨论:

  • 如果 \(f_x\)\(0\) 变为 \(1\)

    \(1\leftrightarrow y\) 这条链上,满足 \(s\ne1\) 的最深的点为 \(z\)

    • 如果 \(z\) 存在,那么 \([y,z]\) 上点的 \(s\) 都要 \(+1\) \([x,z)\) 上点的 \(f\) 都要 \(+1\)\(f_1\) 不变。

    • 如果 \(z\) 不存在,那么 \([y,1]\) 上点的 \(s\) 都要 \(+1\) \([x,1]\) 上点的 \(f\) 都要 \(+1\)

  • 如果 \(f_x\)\(1\) 变为 \(0\)

    \(1\leftrightarrow y\) 这条链上,满足 \(s\ne2\) 的最深的点为 \(z\)

    • 如果 \(z\) 存在,那么 \([y,z]\) 上点的 \(s\) 都要 \(-1\) \([x,z)\) 上点的 \(f\) 都要 \(-1\)\(f_1\) 不变。

    • 如果 \(z\) 不存在,那么 \([y,1]\) 上点的 \(s\) 都要 \(-1\) \([x,1]\) 上点的 \(f\) 都要 \(-1\)

LCT 只需要维护链上的 \(z\) 和链上加标记就好了。

说得挺恶心的,写起来还是挺简单的。

代码

P5354 由乃的OJ(睡觉困难综合征)

题意

给一棵树,每个点有一个运算符 \(opt\) 和一个值 \(v\)\(opt\) 只能是 AND OR XOR 三种。如果数字 \(x\) 经过点 \(i\) 会变成 \(x~opt_i~v_i\)。每次查询三个数 \(x,y,z\),选定一个 \(v\in[0,z]\),然后依次经过 \(x\to y\) 链上的点,求最大可以得到的值。

讲得不是很清楚,详见原题面。

解法 1

思路显然是把 -1ull0 代进这条链算一下,然后 \(O(\log w)\) 的按位贪心。

然后就考虑怎么维护这个东西。

\(sf_{x,0}\)\(0\) 由浅到深地经过 \(x\) 维护的这条链得到的值,\(sf_{x,1}\)-1ull 由浅到深地经过后得到的值。

\(sb_{x,0}\)\(0\) 由深到浅地经过 \(x\) 维护的这条链得到的值,\(sb_{x,1}\)-1ull 由深到浅地经过后得到的值。

那么 reverse 的时候就可以直接 swap \(sf\)\(sb\) 了。

考虑怎么合并两条链。

令要合并的两条链为 \(u,v\),经过链 \(u\) 后,\(x\to p(x)\);经过链 \(v\) 后,\(x\to q(x)\)。举个例子:

\[ \begin{array}{lll} src & x & 111111 \\ p(src) & sf_{u,1} & \color{red}{111}\color{green}{00}\color{red}1 \\ q(src) & sf_{v,1} & \color{red}{110}01\color{red}1 \\ q(0) & sf_{v,0} & 110\color{green}{01}1 \\ p(q(src)) & sf_{x,1} & \color{red}{110}\color{green}{01}\color{red}0 \end{array} \]

所以 \(sf_{x,1}=\color{red}{(sf_{u,1}\operatorname{and}sf_{v,1})}+\color{green}{(\sim\!sf_{u,1}\operatorname{and}sf_{v,0})}\)

同理可得 \(sf_{x,0}=\color{red}{(sf_{u,0}\operatorname{and}sf_{v,1})}+\color{green}{(\sim\!sf_{u,0}\operatorname{and}sf_{v,0})}\)

\(sb\) 只要把 \(u\)\(v\) 反过来就好了。pushup 时记得要合并三条链(两条链 + 一个点)。

然后就做完了。

解法 2

其实本质还是第一种解法。

考虑一道题 Codeforces 879C - Short Program

我们可以把整条链上的操作简化为一次 OR 和一次 XOR。

然后查询出整条链简化后的操作,再按位贪心。

代码

维护子树信息

P4219 大融合

题意

\(n\) 个点,支持连边,查询一条边的负载。边 \((x,y)\) 负载定义为 \(sz_x\cdot sz_y\)

解法

注意本题解法中有很多自创的名词,或者定义与其他地方不同的相同名词,望周知。

LCT 维护子树信息。

因为 Splay 中每个点对应一个区间,所以 LCT 中的每一个点都对应着一条实链的一部分(或者整条实链)。我们称 \(x\) 维护的链中深度最浅的点\(x\)链顶(这个名字是我自己 yy 的)。

\(s_x\)\(x\)链顶的子树大小,\(vs_x\)\(x\) 所有虚儿子的子树大小和,那么可以写出 \(s\) 的 pushup:

\(s_x=s_{\operatorname L(x)}+s_{\operatorname R(x)}+vs_x+1\)

然后考虑如何维护 \(vs\)

考虑这段 access:void ac(int x) { for (int i = 0; x; x = p[i = x]) sp(x), R(x) = i, up(x); }。它将 \(x\) 在 Splay 中的右儿子换成了 \(i\),即 \(\operatorname R(x)\) 从实儿子变成了虚儿子,\(i\) 从虚儿子变成了实儿子。

那么 \(vs_x+s_{\operatorname R(x)}-s_i\to vs_x\)

所以在我们可以在 access 时更新 \(vs\),pushup 时更新 \(s\)

对于每一个查询 \((x,y)\)\(\operatorname{split}(x,y)\) 后,答案就是 \((vs_x+1)(vs_y+1)\)

代码

LOJ #558 我们的 CPU 遭到攻击

题意

给一片森林,边带权,点带黑白,支持 link、cut、反转颜色、求所有与 \(x\) 相连的黑点到 \(x\) 的距离和。保证操作合法。

\(0\le k<n\le10^5,0\le m\le3\times10^5,|w|\le10^7\)

解法

因为 Splay 中每个点对应一个区间,所以 LCT 中的每一个点都对应着一条实链的一部分(或者整条实链)。我们称 \(x\) 维护的链中深度最浅的点\(x\)链顶(这个名字是我自己 yy 的)。

在此我们另 \(x\) 的虚子树为 \(\mathbf x\) 和其所有的虚儿子构成的子树。但是 \(x\) 的虚子树的答案不包括 \(x\) 本身。

不包括的原因大概是虚子树信息不在 pushup 中更新,处理较为麻烦。

\(s_x\)\(x\)链顶的答案,\(vs_x\)\(x\)虚子树的答案。假设我们已经求出了 \(s_{\operatorname L(x)},s_{\operatorname R(x)},vs_x\),现在我们要写出 pushup 的式子。

  • \(\operatorname L(x)\) 的链顶与 \(x\) 的链顶相同,可以直接转移;
  • 如果 \(x\) 是黑点,那么 \(x\) 对链顶的贡献就是 \(x\) 到链顶的距离;
  • \(\operatorname R(x)\) 对链顶的贡献等于 \(s_{\operatorname R(x)}\) 加上 \(\operatorname R(x)\) 中黑点的个数与 \(x\) 到链顶的距离的乘积。

根据套路,处理边权可以将边构点。把边权化为点权。如果点维护的是原树中的边,那么点权等于边权,否则点权为 \(0\)。令 \(x\) 的点权为 \(v_x\)\(x\) 对应的链的点权和为 \(d_x\)

那么 \(x\) 到链顶的距离就是 \(v_x+d_{\operatorname L(x)}\)

然后令 \(col_x\)\(x\) 的颜色(黑点为 \(1\)),\(c_x\)\(x\)链顶的黑点个数,\(vc_x\)\(x\)虚子树的黑点个数。在 access 时维护 \(vc_x\)\(c_x=c_{\operatorname L(x)}+c_{\operatorname R(x)}+vc_x+col_x\)

还有一个问题,makeroot 时需要打 reverse 标记。所以还要维护 \(\operatorname L(x),\operatorname R(x)\) 反转后的 \(s_x\),记做 \(s'_x\)

那么综合上面的分类讨论,可以写出 \(s,s',c,d\) 的 pushup:

\[ \begin{cases} s_x=s_{\operatorname L(x)}+s_{\operatorname R(x)}+vs_x+(c_{\operatorname R(x)}+vc_x+col_x)(v_x+d_{\operatorname L(x)}),\\ s'_x=s'_{\operatorname R(x)}+s'_{\operatorname L(x)}+vs_x+(c_{\operatorname L(x)}+vc_x+col_x)(v_x+d_{\operatorname R(x)}),\\ c_x=c_{\operatorname L(x)}+c_{\operatorname R(x)}+vc_x+col_x,\\ c_x=c_{\operatorname L(x)}+c_{\operatorname R(x)}+v_x,\\ \end{cases} \]

然后在 access 的时候维护 \(vs,vc\),在 reverse 的时候 swap \(s,s'\) 就好了。

代码

写代码的时候被卡了常,可能是我人比较丑,水平比较低吧……

维护生成树

UOJ #274 温暖会指引我们前行

题意

给一片森林(\(n\) 个点),支持连一条 \((x,y,t,l)\) 的边(\(t,l\) 为权值),改变一条边的 \(l\) 值,查询两个点之间所有路径中,\(t\) 值升序排序后字典序最大的路径的 \(l\) 值和。

注意本题中的字典序与传统意义上的字典序定义有所不同,对于两个序列 \(a,b(a\ne b)\),若 \(a\)\(b\) 的前缀则 \(a\) 的字典序较大,同时可以推出空串的字典序最大。

\(1\le n\le10^5,1\le m\le3\times10^5\),每条边的 \(t\) 互不相同。

解法

查询操作显然是要最大化路径上的最小 \(t\) 值。那么可以考虑二分最大生成树。

可以证明,查询的路径一定在最大生成树上。那么只需要用 LCT 维护最大生成树。

每在图中加一条边 \((x,y,t_0)\) 时(我们要的是 \(t\) 的最大生成树),分下面几类讨论:

  • 如果 \(x,y\) 不连通,直接连边;
  • 如果 \(x,y\) 连通且 \(x\leftrightarrow y\) 的路径上最小的 \(t\) 值大于 \(t_0\),那么会使得边权和变小,不连边;
  • 否则断掉 \(t\) 值最小的边,然后连上 \((x,y,t_0)\)

还是根据套路,边转换为虚点。那么 pushup 时需要维护的就是当前链上权值最小的点的编号。

代码

维护 DCC / 广义圆方树

P2542 航线规划

题意

给一张图,支持查询链上割边数,断边。

\(1\le n,m\le3\times10^4,1\le q\le4\times10^4\)

解法

严格来说,我这种解法应该归为 维护链上信息 才对……

根据套路,离线处理,操作逆序,断边变连边。

然后维护 \(v_i\):如果 \(i\) 是割边,那么 \(v_i=1\);如果 \(i\) 是点或不是割边,那么为 \(0\)

然后分类讨论连边的情况(连接 \((x,y)\)):

  • \(x\)\(y\) 不连通

    直接连边,\(v\) 设为 \(1\)

  • \(x\)\(y\) 连通

    \(\operatorname{split}(x,y)\),然后把中间所有边的 \(v\) 设为 \(0\)

代码

终于 1A 了……太开心了 >_<

P4320 道路相遇

题意

给一张图,每次查询两个数 \(x,y\),求 \(x\)\(y\) 的必经点数。

\(1\le n,m\le5\times10^5\)

解法

注意到 v-DCC 内部一定没有必经点,考虑维护原图的广义圆方树。

那么每次连接 \((x,y)\) 时,分类讨论:

  • 如果 \(x,y\) 不连通,直接连接 \(x,y\) 即可。
  • 如果 \(x,y\) 连通,将 \(x\leftrightarrow y\) 上的点全部缩成一个点。具体如下:

    split 出 \(x\leftrightarrow y\),按照深度顺序做一次 DFS,然后把链上的边全部断掉。

    然后开一个新点(方点),把 \(x\leftrightarrow y\) 的点全部连向这个新点。

我们要求的实际上是 \(x\leftrightarrow y\) 上的圆点数。直接维护即可。

显然每个点被缩的次数是 \(O(1)\) 的,复杂度可以保证。

代码

U76146 一道LCT水题

题意

给一张图,支持加边,查询 \(x\leftrightarrow y\) 必经点、必经边。

\(1\le n\le10^5,1\le q\le3\times10^5\),强制在线。

解法

考虑与上题类似的方法。注意到如果对点构边,上题的做法可以直接套用。

然后就做完了一道鱼题 OwO!

代码