题解：P9867 [POI 2021/2022 R2] kon

· · 题解

前言

题目链接：洛谷。

庚昊的体验。

题意简述

维护一张无向图图，初始两个点，通过一条边相连。q 次操作：

题目分析

妙妙题。

发现 Z 操作很像把 x 复制一遍，相当于一个新的版本。提示我们对操作建树，u 继承了 \operatorname{fa}(u) 所有对应的连边状态。

那么 W 操作就是先把 x 复制一遍，在新版 x 上与新建点「连边」（这里连边是原图上相连的意思，并非树边，称之为「W 边」），这样不会让之前的点错误继承这次操作。

原图上，两个点 u,v 相连，当且仅当操作树上 u 的某一个祖先 u' 和 v 的某一个祖先 v'，通过 W 边相连。

那么问题变为了求 x 的每一个祖先，所有连出 W 边指向的点，在操作树上的子树中有几个点，这里需要对点做区分，不能算上 W 操作复制的版本。

稍微分类讨论一下。对于树根，相当于单点加子树和；对于非树根，修改的时候将树根 W 边父亲单点修改，链查询。

均可以树状数组做到 \mathcal{O}(n\log n)。

可以 LCT 做到在线，相信大家都会。

代码

离线树状数组、在线 LCT 的代码，见我博客。